Pada masalah Jalur-Jalur Terpendek Sumber-Tunggal (Single-Source Shortest Paths, SSSP), kita bertujuan untuk menemukan bobot jalur-jalur terpendek dari sebuah simpul sumber-tunggal (dan juga jalur-jalur tersebut) ke semua simpul lainnya dalam sebuah graf terarah dan berbobot (bila jalur-jalur tersebut ada).

SSSP is one of the most frequent graph problem encountered in real-life. Every time we want to move from one place (usually our current location) to another (our destination), we will try to pick a short — if not the shortest — path.

SSSP algorithm(s) is embedded inside various map software like Google Maps and in various Global Positioning System (GPS) tool.

Masukan 1: Sebuah graf terarah berbobot G(V, E), tidak harus terhubung, dimana V/simpul-simpul bisa digunakan untuk mendeskripsikan vertices can be used to describe persimpangan, rumah, tempat terkenal, dsb dan E/sisi-sisi bisa digunakan untuk mendeskripsikan jalan(-jalan) dengan arah tertentu dan bobot/biaya.

Masukan 2: Seperti namanya, masalah SSSP memiliki masukan lain: Sebuah simpul sumber s ∈ V.

Tujuan dari masalah SSSP adalah untuk menemukan bobot jalur terpendek dari s ke setiap simpul u ∈ V, yang dilambangkan sebagai δ(s, u) (δ dibaca sebagai 'delta') dan juga jalur terpendek yang sesungguhnya dari s ke u.

Bobot jalur dari jalur p secara sederhana adalah penjumlahan dari bobot-bobot sisi sepanjang jalur tersebut.

Bobot dari jalur terpendek dari s ke s adalah sepele: 0.
Bobot dari jalur terpendek dari s ke simpul yang tidak terjangkau juga sepele: +∞.

Catatan: Bobot dari jalur terpendek dari s ke v dimana (s, v) ∈ E tidak harus selalu adalah bobot dari w(s, v). Lihat beberapa slide berikutnya untuk menyadari hal ini.

Keluaran-keluaran dari semua enam (6) algoritma-algoritma SSSP untuk masalah SSSP yang didiskusikan dalam visualisasi ini adalah kedua larik/Vector berikut:

1. Sebuah larik/Vector D dengan ukuran V (D adalah 'distance' atau 'jarak')
   Pada awalnya, D[u] = 0 jika u = s; kalau tidak D[u] = +∞ (angka besar seperti 10⁹)
   D[u] berkurang ketika kita menemukan jalur-jalur yang lebih baik (lebih pendek)
   D[u] ≥ δ(s, u) sepanjang eksekusi dari algoritma SSSP
   D[u] = δ(s, u) pada akhir algoritma SSSP
2. Sebuah larik/Vector p dengan ukuran V (p adalah 'parent'/'predecessor'/'previous')
   p[u] = pendahulu dari jalur terbaik dari sumber s ke u
   p[u] = NULL (tidak didefinisikan, kita bisa menggunakan nilai seperti -1 untuk ini)
   Larik/Vector p ini mendeskripsikan pohon perentang SSSP yang dihasilkan

Initially, D[u] = +∞ (practically, a large value like 10⁹) ∀u ∈ V\{s}, but D[s] = D[0] = 0.
Initially, p[u] = -1 (to say 'no predecessor') ∀u ∈ V.

Now click Dijkstra(0) — don't worry about the details as they will be explained later — and wait until it is over (approximately 10s on this small graph).

At the end of that SSSP algorithm, D[s] = D[0] = 0 (unchanged) and D[u] = δ(s, u) ∀u ∈ V
e.g., D[2] = 6, D[4] = 7 (these values are stored as red text under each vertex).
At the end of that SSSP algorithm, p[s] = p[0] = -1 (the source has no predecessor), but p[v] = the origin of the red edges for the rest, e.g., p[2] = 0, p[4] = 2.

Thus, if we are at s = 0 and want to go to vertex 4, we will use shortest path 0 → 2 → 4 with path weight 7. In the exploration mode, after any SSSP algorithm has been completed, you can hover on any vertex and notice the shortest path from source vertex s to that vertex is highlighted.

Beberapa graf memiliki sisi(-sisi) berbobot negatif (tidak harus bersiklus) dan/atau siklus(-siklus) berbobot negatif. Contohnya (fiksi): Misalkan anda dapat berjalan maju dalam waktu (normal, sisi-sisi dengan bobot positif) atau mundur dalam waktu dengan melalui terowongan waktu (sisi-sisi wormhole spesial dengan bobot negatif), seperti yang ditunjukkan diatas.

Pada graf tersebut, jalur-jalur terpendek dari simpul sumber s = 0 ke simpul-simpul {1, 2, 3} semuanya tidak-jelas. Contohnya 1 → 2 → 1 adalah sebuah siklus berbobot negatif karena memiliki bobot total jalur (siklus) negatif sebesar 15-42 = -27. Oleh karena itu kita bisa berputar-putar didalam siklus berobot negatif 0 → 1 → 2 → 1 → 2 → ... selamanya untuk mendapatkan bobot jalur terpendek yang tidak-jelas sebesar -∞.

Tetapi, sadari bahwa jalur terpendek dari simpul sumber s = 0 ke simpul 4 sebenarnya ok dengan δ(0, 4) = -99. Jadi keberadaan sisi(-sisi) berbobot negatif bukanlah isu utama. Isu utama adalah keberadaan siklus(-siklus) berbobot negatif yang bisa terjangkau dari simpul sumber s.

Operasi utama untuk semua algoritma-algoritma SSSP yang dibahas di visualisasi ini adalah operasi relax(u, v, w(u, v)) dengan pseudo-code sebagai berikut:

relax(u, v, w_u_v)
  if D[v] > D[u]+w_u_v // if jalurnya bisa diperpendek
    D[v] = D[u]+w_u_v // kita 'relax' sisi ini
    p[v] = u // ingat/mutakhirkan pendahulu
    // mutakhirkan struktur data lainnya seperlunya

Contohnya, lihat operasi relax(1,2,4) di gambar dibawah:

There are four different sources for specifying an input graph:

1. Edit Graph: You can edit or (re-)draw currently shown directed weighted graph.
2. Input Graph: You can input a graph (in Edge List/Adjacency List/Adjacency Matrix format) and VisuAlgo will propose a 2D graph drawing for your graph.
3. Example Graphs: You can select from the list of our selected example graphs to get you started. These example graphs have different characteristics.
4. NEW (Oct 24): An NUS student created the following maze/grid-based graph drawing tool that can be quickly used to create a maze/grid graph that can be exported back to this sssp visualization page.

Dalam visualisasi ini, kita akan membahas 6 (ENAM) algoritma-algoritma SSSP.

Kita akan mulai dengan algoritma O(V×E) Bellman-Ford terlebih dahulu karena algoritma ini adalah algoritma SSSP yang paling serba guna (tetapi juga yang terlambat). Kita lalu akan membahas 5 (LIMA) algoritma-algoritma lainnya (termasuk dua varian dari algoritma Dijkstra) yang menyelesaikan kasus-kasus spesial dari masalah-masalah SSSP dalam waktu yang jauh lebih cepat.

Algoritma Bellman-Ford yang serba guna dapat digunakan untuk menyelesaikan seluruh varian masalah SSSP yang valid (kecual satu — yang tidak jelas, akan dibahas segera), meskipun waktu yang cukup lambat O(V×E). Algoritma ini juga memiliki pseudo-code yang sangat sederhana:

for i = 1 to |V|-1 // O(V) disini, jadi O(V×E×1) = O(V×E)
  for each edge(u, v) ∈ E // O(E) disini, misalkan dengan Daftar Sisi
    relax(u, v, w(u, v)) // O(1) disini

Tanpa basa-basi lagi, mari lihat sekilas bagaimana algoritma ini bekerja pada graf contoh diatas dengan mengklik BellmanFord(0) (≈30s, dan untuk saat ini, tolong abaikan loop tambahan yang ada di bagian bawah dari pseudo-code).

Algoritma Bellman-Ford bisa dibuat untuk berjalan sedikit lebih cepat pada graf masukan normal, dari kasus terjelek O(V×E) ke hanya (k×E) dimana k adalah jumlah iterasi dari loop luar Bellman Ford.

Diskusi: Bagaimana caranya melakukan ini? Apakah percepatan ini signifikan?

Untuk meyakinkan pembaca diseluruh dunia bahwa algoritma Bellman-Ford benar, mari sementara berpindah dari mode visualisasi ke mode pembuktian pada beberapa slide selanjutnya.

Teorema 1: Jika G = (V, E) tidak memiliki siklus berbobot negatif, maka jalur terpendek p dari simpul sumber s ke sebuah simpul v pastilah sebuah jalur sederhana.

Ingat: Sebuah jalur sederhana adalah sebuah jalur p = {v₀, v₁, v₂, ..., v_k}, (v_i, v_i+1) ∈ E, ∀ 0 ≤ i ≤ (k-1) dan tidak ada simpul yang diulang sepanjang jalur ini.

1. Misalkan jalur terpendek p bukanlah jalur sederhana
2. Maka p haruslah memiliki satu (atau lebih) siklus(-siklus) (oleh karena definisi dari jalur yang tidak-sederhana)
3. Misalkan ada siklus c dalam p dengan bobot positif (yaitu hijau → biru → hijau pada gambar di sisi kiri)
4. Jika kita menghapus c dari p, maka kita akan memiliki 'jalur terpendek' yang lebih pendek daripada jalur terpendek p kita
5. Sebuah kontradiksi yang jelas sekali, maka p pastilah sebuah jalur sederhana

6. Meskipun jika c sebenarnya adalah sebuah siklus dengan bobot total nol (0) — ini memungkinkan menurut asumsi Teorema 1 kita: tidak ada siklus berbobot negatif (lihat hijau → biru → hijau yang sama tetapi pada gambar di sisi kanan), kita tetap bisa menghapus c dari p tanpa menambah bobot jalur terpendek dari p
7. Secara kesimpulan, p adalah jalur sederhana (dari poin no 5) atau selalu bisa dijadikan jalur sederhana (dari poin 6)

Dengan kata lain, jalur terpendek p memiliki paling banyak |V|-1 sisi-sisi dari simpul sumber s ke simpul 'yang paling jauh' v dalam G (mengenai jumlah sisi-sisi pada jalur terpendek — lihat contoh Bellman-Ford Killer diatas).

Teorema 2: Jika G = (V, E) tidak memiliki siklus berbobot negatif, maka setelah algoritma Bellman-Ford berhenti, kita akan mempunyai D[v] = δ(s, u), ∀ u ∈ V.

Untuk ini, kita akan menggunakan Pembuktian Induksi (Proof by Induction) dan inilah poin-poin awalnya:

Pertimbangkan jalur terpendek p dari simpul sumber s ke simpul v_i dimana v_i didefinisikan sebagai sebuah simpul dimana jalur terpendek sesungguhnya untuk mencapai simpul tersebut membutuhkan i loncatan (sisi) dari simpul sumber s. Ingat kembali dari Teorema 1 bahwa p adalah sebuah jalur sederhana karena kita memiliki asumsi yang sama tentang tidak adanya siklus berbobot negatif.

1. Pada awalnya, D[v₀] = δ(s, v₀) = 0, karena v₀ adalah simpul sumber s
2. Setelah 1 pass melalui E, kita punya D[v₁] = δ(s, v₁)
3. Setelah 2 pass melalui E, kita punya D[v₂] = δ(s, v₂)
4. ...
5. Setelah k pass melalui E, kita punya D[v_k] = δ(s, v_k)
6. Ketika tidak ada siklus berbobot negatif, jalur terpendek p adalah jalur sederhana (lihat Teorema 1), maka iterasi terakhir adalah iterasi |V|-1
7. Setelah |V|-1 pass melalui E, kita punya D[v_|V|-1] = δ(s, v_|V|-1), tidak memperdulikan pengurutan sisi-sisi dalam E — lihat contoh Bellman-Ford Killer diatas

Cobalah jalankan BellmanFord(0) pada contoh 'Bellman-Ford Killer' diatas. Ada V = 7 simpul-simpul dan E = 6 sisi-sisi tetapi daftar sisi E dikonfigurasikan dengan urutan yang paling jelek. Sadari bahwa setelah (V-1)×E = (7-1)*6 = 36 operasi-operasi (~40s, sabarlah), Bellman-Ford akan berhenti dengan jawaban yang benar dan tidak mungkin kita bisa memberhentikan algoritma Bellman-Ford lebih cepat.

Satu-satunya graf masukan yang algoritma Bellman-Ford memiliki isu adalah graf masukan dengan siklus berbobot negatif yang terjangkau dari simpul sumber s.

Tetapi, Bellman-Ford dapat digunakan untuk mendeteksi apabila graf masukan memiliki setidaknya satu siklus berbobot negatif yang terjangkau dari simpul sumber s dengan menggunakan akibat wajar dari Teorema 2: Jika setidaknya satu nilai D[v] gagal converge setelah |V|-1 pass, maka pastilah ada siklus berbobot-negatif yang terjangkau dari simpul sumber s.

Sekarang jalankan BellmanFord(0) pada graf contoh yang memiliki sisi-sisi negatif dan sebuah siklus negatif. Silahkan konsentrasi pada loop dibawah pseudo-code.

Kadang-kadang, masalah sebenarnya yang kita hadapi bukanlah bentuk umum dari masalah orisinalnya. Oleh karena itu dalam Kuliah Maya ini, kami mau menyorot lima (5) kasus-kasus spesial berhubungan dengan masalah SSSP. Ketika kita berhadapan dengan salah satu dari mereka, kita bisa menyelesaikannya dengan algoritma berbeda dan (jauh) lebih cepat dibandingkan dengan algoritma generik O(V×E) Bellman Ford. Mereka adalah:

1. Pada Graf-Graf Tidak-Berbobot: O(V+E) BFS,
2. Pada Graf-Graf tanpa bobot negatif: O((V+E) log V) algoritma Dijkstra,
3. Pada Graf-Graf tanpa siklus berbobot negatif: O((V+E) log V) Dijkstra dengan Modifikasi,
4. Pada Pohon: O(V+E) DFS/BFS,
5. Pada Graf Terarah Tidak-bersiklus (Directed Acyclic Graphs, DAG): O(V+E) Pemrograman Dinamis (Dynamic Programming, DP)

The O(V+E) Breadth-First Search (BFS) algorithm can solve special case of SSSP problem when the input graph is unweighted (all edges have unit weight 1, try BFS(5) on example: 'CP4 4.2 U/U' above) or positive constant weighted (all edges have the same constant weight, e.g. you can change all edge weights of the example graph above with any positive constant weight of your choice).

Ketika grafnya tidak-berbobot — ini muncul cukup sering dalam kehidupan nyata — masalah SSSP dapat dilihat sebagai sebuah masalah untuk mencari jumlah sisi-sisi tersedikit yang dikunjungi dari simpul sumber s ke simpul-simpul lainnya.

Pohon perentang BFS dari simpul sumber s yang diproduksi oleh algoritma O(V+E) BFS yang cepat — sadari simbol + — secara cocok memenuhi kebutuhan.

Bandingkan dengan O(V×E) dari Bellman-Ford — sadari simbol × — adalah tepat untuk menggunakan BFS untuk kasus spesial dari masalah SSSP ini.

Dibandingkan dengan BFS standar dalam modul Penjelajahan Graf, kita melakukan modifikasi-modifikasi sederhana untuk membuat BFS bisa menyelesaikan versi tidak berbobot dari masalah SSSP:

1. Pertama, ubah larik Boolean visited menjadi sebuah larik Bilangan Bulat D.
2. Pada awal BFS, daripada mengeset visited[u] = false, kita mengeset D[u] = 1e9 (sebuah angka yang besar untuk menyimbolkan +∞ atau bahkan -1 untuk menyimbolkan status 'belum dikunjungi', tetapi kita tidak bisa menggunakan 0 karena D[0] = 0) ∀u ∈ V\\{s}; Lalu kita mengeset set D[s] = 0
3. Kita mengubah loop utama dari BFS dari
   if (visited[v] = 0) { visited[v] = 1 ... } // v belum dikunjungi
   ke
   if (D[v] = 1e9) { D[v] = D[u]+1 ... } // v = 1 langkah dari u

Tetapi, BFS akan sangat mungkin memberikan jawaban salah ketika dijalankan pada graf berbobot karena BFS tidak didesain untuk menyelesaikan versi berbobot dari masalah SSSP. Mungkin ada kasus dimana mengambil jalur dengan jumlah sisi-sisi yang lebih banyak memproduksi bobot jalur total yang lebih rendah daripada mengambil jalur dengan jumlah sisi-sisi paling sedikit — yang adalah keluaran dari algoritma BFS.

Dalam visualisasi ini, kami akan mengijinkan anda untuk menjalankan BFS bahkan pada graf masukan yang 'salah' untuk alasan pedagogis, tetapi kami akan menampilkan pesan peringatan di akhir algoritma. Contohnya, coba BFS(0) pada graf umum diatas dan anda akan melihat bahwa simpul-simpul {3,4} akan memiliki nilai-nilai D[3] dan D[4] yang salah (dan juga nilai-nilai p[3] dan p[4]).

Kita akan segera melihat algoritma Dijkstra (2 varian implementasi) untuk menyelesaikan masalah-masalah SSSP tertentu jauh lebih cepat daripada algoritma Bellman-Ford yang lebih umum.

The O((V+E) log V) Dijkstra's algorithm is the most frequently used SSSP algorithm for typical input: Directed weighted graph that has no negative weight edge, formally: ∀edge(u, v) ∈ E, w(u, v) ≥ 0. Such weighted graph (especially the positive weighted ones) is very common in real life as travelling from one place to another always use positive time unit(s). Try Dijkstra(0) on one of the Example Graphs: CP4 4.16* D/W shown above (compared to CP4 version, we add one more edge 2 → 1 to make the graph non-DAG).

Algoritma Dijkstra menjaga sebuah set R (Resolved/terselesaikan) — literatur lain menggunakan himpunan S (Solved) tetapi himpunan S dan simpul source s terlalu mirip ketika diucapkan — dari simpul-simpul yang dimana bobot-bobot jalur terpendek finalnya sudah ditentukan. Pada awalnya R = {}, kosong.

Lalu, algoritma ini secara berulang memilih simpul u dalam {V\\R} (juga dapat ditulis sebagai {V-R}) dengan estimasi jalur terpendek minimum (simpul pertama yang dipilih adalah u = s, karena hanya D[s] = 0 dan simpul lainnya mempunyai D[u] = ∞), menambahkan u ke R, dan merelaksasi semua sisi-sisi keluar dari u. Penjelasan detil dari pembuktian kebenaran dari algoritma Dijkstra ini biasanya ditulis di buku-buku teks Ilmu Komputer. Untuk penjelasan visual intuitif yang lebih mudah mengenai kenapa strategi rakus (greedy) ini bekerja, lihat artikel ini.

Ini memerlukan penggunaan sebuah Antrean Berprioritas (Priority Queue) karena estimasi-estimasi jalur terpendek berubah-ubah terus saat lebih banyak lagi sisi-sisi diproses. Keputusan untuk merelaksasi sisi-sisi keluar yang berasal dari simpul dengan estimasi jalur terpendek minimum adalah rakus (greedy), yaitu gunakan "yang terbaik sejauh ini", tetapi kita akan lihat nanti bahwa bisa dibuktikan bahwa strategi ini pada akhirnya berakhir dengan hasil yang optimal — jika grafnya tidak memiliki sisi berbobot negatif.

Dalam algoritma Dijkstra, setiap simpul hanya akan diekstrak dari Antrean Berprioritas (Priority Queue, PQ) sekali saja. Karena ada V sisi-sisi, kita akan melakukan ini paling banyak O(V) kali.

Operasi EkstrakMin() berjalan dalam O(log V) tidak masalah apakah PQnya diimplementasikan menggunakan sebuah Timbunan Biner Minimum atau menggunakan sebuah BST seimbang seperti Pohon AVL.

Oleh karena itu, bagian ini adalah O(V log V).

Setiap kali sebuah simpul diproses, kita merelaksasi tetangga-tetangganya. Secara total, E sisi-sisi diproses.

Jika dengan merelaksasi sisi(u, v), kita harus menurunkan D[v], kita akan memanggil operasi O(log V) DecreaseKey() dalam Timbunan Biner Minimum (susah untuk diimplementasikan karena C++ STL priority_queue/Python heapq/Java PriorityQueue saat ini tidak mendukung operasi ini secara efisien) atau secara sederhana hapus dat lama dan masukkan ulang data baru dalam BST seimbang seperti Pohon AVL (yang juga berjalan dalam O(log V), tetapi ini jauh lebih mudah untuk diimplementasikan, cukup gunakan C++ STL set/Java TreeSet — sayang sekali tidak didukung secara natif dalam Python).

Oleh karena itu, bagian ini adalah O(E log V).

Jadi secara keseluruhan, algoritma Dijkstra berjalan dalam waktu O(V log V + E log V) = O((V+E) log V), yang adalah jatuh lebih cepat daripada algoritma O(V×E) Bellman Ford.

Untuk menunjukkan kebenaran algoritma Dijkstra pada graf berbobot non-negatif, kita perlu menggunakan invarian loop: kondisi yang Benar pada awal setiap iterasi loop.

Kita ingin menunjukkan:

• Inisialisasi: Invarian loop benar sebelum iterasi pertama.
• Pemeliharaan: Jika invarian loop benar untuk iterasi x, maka tetap benar untuk iterasi x+1.
• Terminasi: Ketika algoritma berakhir, invarian loop membantu pembuktian kebenaran.

Diskusi: Buktikan secara formal kebenaran algoritma Dijkstra di kelas!

When the input graph contains at least one negative weight edge — not necessarily negative weight cycle — Dijkstra's algorithm can produce wrong answer.

Try Dijkstra(0) on one of the Example Graphs: CP4 4.20.

At the end of the execution of Dijkstra's algorithm, vertex 4 has wrong D[4] value as the algorithm started 'wrongly' thinking that subpath 0 → 1 → 3 is the better subpath of weight 1+2 = 3, thus making D[4] = 6 after calling relax(3,4,3). However, the presence of negative weight -10 at edge 2 → 3 makes the other subpath 0 → 2 → 3 eventually the better subpath of weight 10-10 = 0 although it started worse with path weight 10 after the first edge 0 → 2. This better D[3] = 0 is never propagated further due to the greedy nature of Dijkstra's algorithm, hence D[4] is wrong.

Dijkstra's algorithm can also be implemented differently. The O((V+E) log V) Modified Dijkstra's algorithm can be used for directed weighted graphs that may have negative weight edges but no negative weight cycle.

Such input graph appears in some practical cases, e.g., travelling using an electric car that has battery and our objective is to find a path from source vertex s to another vertex that minimizes overall battery usage. As usual, during acceleration (or driving on flat/uphill road), the electric car uses (positive) energy from the battery. However, during braking (or driving on downhill road), the electric car recharges (or use negative) energy to the battery. There is no negative weight cycle due to kinetic energy loss.

For example, try ModifiedDijkstra(0) on one of the Example Graphs: CP4 4.20 that has troubled the original version of Dijkstra's algorithm (see previous slide).

Ide kuncinya adalah modifikasi yang dilakukan kepada C++ STL priority_queue/Python heapq/Java PriorityQueue untuk menginjikannya melakukan operasi 'DecreaseKey' secara efisien, yaitu dalam waktu O(log V).

Teknik ini disebut 'Pemutakhiran Malas (Lazy Update)' dimana kita meninggalkan 'informasi yang kadaluarsa/lebih lemah/bernilai lebih besar' didalam Antrean Berprioritas minimum daripada menghapusnya langsung. Karena item-item terurut dari nilai-nilai yang lebih kecil ke nilai-nilai yang lebih besar didalam sebuah PQ minimum, kita mengaransi diri sendiri bahwa kita akan menjumpai item yang paling kecil/paling mutakhir terlebih dahulu sebelum menjumpai item(-item) yang lebih lemah/kadaluarsa nantinya - yang bisa dengan mudah tidak diperdulikan.

Pada graf-graf berbobot tidak-negatif, perilaku dari implementasi Dijkstra termodifikasi tepat sama dengan versi orisinal Dijkstra jadi kita bisa menggunakan analisa kompleksitas waktu yang sama yaitu O((V+E) log V).

Catatan: Kita menyadari bawah ketika kita menggunakan algoritma Dijkstra termodifikasi, bisa lebih banyak item-item (bisa sebesar E) dalam Antrean Berprioritas daripada jika kita menggunakan algoritma Dijkstra Orisinil (hanya sebesar V). Tetapi, karena O(log E) = O(log V^2) = O(2 log V) = O(log V), kita masih bisa menganggap operasi-operasi Antrean Berprioritas sebagai O(log V).

Tetapi, jika grafnya memiliki setidaknya satu sisi berbobot negatif, analisanya lebih susah.

When the input graph contains at least one negative weight edge but no negative weight cycle — the modified Dijkstra's algorithm produces correct answer.

Try ModifiedDijkstra(0) on one of the Example Graphs: CP4 4.20 that causes problem for Dijkstra(0).

At the end of the execution of ModifiedDijkstra's algorithm, vertex 4 has correct D[4] value as although the modified Dijkstra's algorithm also started 'wrongly' thinking that subpath 0 → 1 → 3 is the better subpath of weight 1+2 = 3, thus making D[4] = 6 after calling relax(3,4,3). Here, the modified Dijkstra's algorithm continues propagating D[3] = 0 after it founds out that the other subpath 0 → 2 → 3 is eventually the better subpath of weight 10-10 = 0. Hence D[4] is eventually correct again. However, this is at the expense of potentially running (much more) operations than O((V+E) log V).

Unfortunately, running ModifiedDijkstra(0) on the graph with negative weight cycle as shown on one of the Example Graphs: CP4 4.22 above will cause an endless loop (the animation is very long but we limit the number of loop to be 100 edges processed so your web browser will not hang).

Coba ModifiedDijkstra(0) pada contoh kasus sudut ekstrim diatas yang sangat susah untuk dibuat tanpa pengertian yang mendalam tentang algoritma ini dan yang adalah bagian dari tugas Asia Pacific Informatics Olympiad (APIO) 2013 yang dibuat oleh A/P Halim sendiri beberapa tahun yang lalu.

Algoritma Dijkstra termodifikasi akan berhenti dengan jawaban yang benar, tetapi hanya setelah menjalankan operasi-operasi yang berjumlah eksponensial (setiap segitiga yang dibuat dengan hati-hati menaikkan jumlah operasi-operasi yang dibutuhkan dengan satu lagi pangkat dua). Oleh karena itu, kita tidak bisa secara prematur menghentikan Dijkstra termodifikasi pada situasi masukan kasus terjelek ini.

Tetapi, kasus sudut ekstrim seperti ini sangat jarang sehingga pada prakteknya, algoritma Dijkstra termodifikasi bisa digunakan pada graf-graf terarah yang memiliki beberapa sisi-sisi berbobot negatif sepanjang graf tersebut tidak memiliki siklus berbobot negatif yang terjangkau dari simpul sumber s.

Algoritma O(V+E) Depth-First-Search (DFS) dapat menyelesaikan kasus spesial dari masalah SSSP, yaitu ketika graf masukannya adalah sebuah pohon (berbobot).

Dalam sebuah Pohon, hanya ada satu jalur unik dan tidak-bersiklus yang menghubungkan dua simpul yang berbeda. Sehingga jalur unik yang menghubungkan simpul sumber s ke simpul lain u ∈ V sebernarnya juga adalah jalur terpendek. Contohnya, coba DFS(0) pada Pohon diatas.

Catat bahwa untuk sebuah Pohon (berbobot), kita juga dapat menggunakan BFS. Contohnya, coba BFS(0) pada Pohon yang sama diatas.

Diskusi: Kenapa DFS (dan juga BFS) berjalan dalam O(V) dan bukan dalam O(V+E) jika masukannya adalah sebuah Pohon (berbobot)?

DFS sangat mungkin menghasilkan jawaban yang salah ketika dijalankan pada graf lain yang bukan Pohon. Kami akan menampilkan pesan peringatan untuk kasus-kasus tersebut meskipun kami tidak melarang anda untuk mencoba fitur ini untuk alasan pedagogis.

Contohnya, coba DFS(0) pada graf umum diatas dan anda akan melihat bahwa simpul {4} akan memiliki nilai D[4] yang salah (dan juga nilai p[4] yang salah) karena DFS(0) pergi kedalam 0 → 1 → 3 → 4 dahulu, kembali ke simpul 0 dan lalu mengunjungi 0 → 2 tetapi sisi 2 → 4 tidak bisa diproses karena simpul 4 sudah dikunjungi oleh DFS sebelumnya.

Algoritma O(V+E) Pemrograman Dinamis (Dynamic Programming) dapat menyelesaikan kasus spesial dari masalah SSSP, yaitu ketika graf masukannya adalah sebuah Graf Terarah Tidak-bersiklus (Directed Acylic Graph, DAG), sehingga kita dapat menemukan setidaknya satu urutan topologis dari DAG tersebut dan memproses relaksasi sisi berdasarkan urutan topologis tersebut.

Pada contoh Modified Dijkstra's killer diatas, DP(0) bekerja dengan cepat karena graf tersebut sebenarnya adalah sebuah DAG, meskipun memiliki sisi berbobot negatif. Karena grafnya adalah DAG, maka tidak akan ada siklus berbobot negatif yang perlu diperhatikan.

Tetapi, DP tidak akan bekerja untuk graf yang bukan DAG karena graf yang bukan DAG memiliki setidaknya satu siklus dan oleh karena itu tidak ada urutan topologis yang bisa ditemukan didalam siklus tersebut.

Algoritma DP untuk menyelesaikan SSSP pada DAG juga disebut sebagai algoritma Bellman-Ford satu-laluan karena algoritma tersebut mengganti V-1 loop paling luar (kita tidak tahu urutan yang benar jadi kita ulangi saja sampai yang paling maksimum) dengan hanya satu pass urutan topologis (kita tahu bahwa ini adalah (salah satu) dari urutan(-urutan) yang benar dari DAG ini).

Bandingkan DP(0) (relaksasi E sisi-sisi sekali saja — menurut urutan topologis dari sisi-sisinya) dibandingkan dengan BellmanFord(0) (relaksasi E sisi-sisi dalam urutan acak, sebanyak V-1 kali) pada DAG contoh yang sama diatas.

Kami memiliki banyak hal-hal lain diatas penjelasan dasar dari algoritma-algoritma SSSP untuk masalah-masalah SSSP ini.

Untuk beberapa pertanyaan-pertanyaan menarik tentang masalah SSSP dan berbagai algoritma-algoritmanya, silahkan latihan pada modul latihan SSSP (tidak perlu login).

Tetapi untuk pengguna yang telah teregistrasi, anda sebaiknya login dan lalu pergi ke Halaman Latihan Utama untuk secara resmi menyelesaikan modul ini (setelah menyelesaikan modul-modul prasyarat lainnya) dan prestasi tersebut akan dicatat dalam akun pengguna anda.

Kami juga mempunyai beberapa masalah-masalah pemrograman yang membutuhkan penggunaan algoritma SSSP yang tepat: Kattis - hidingplaces dan Kattis - shortestpath1.

Cobalah selesaikan mereka dan lalu cobalah lebih banyak varian menarik dari masalah SSSP menarik ini.

Iklan: Beli buku teks Competitive Programming untuk membaca lebih banyak tentang masalah yang menarik ini.