7    VisuAlgo.net / /sssp Login Jarak Terpendek Sumber-Tunggal
Mode Eksplorasi ▿

>

>
pelan
cepat
go to beginning previous frame pause play next frame go to end

Pada masalah Jarak 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).


Masalah SSSP adalah sebuah masalah Ilmu Komputer (Computer Science, CS) yang umum-diketahui sehingga semua murid-murid CS di seluruh dunia perlu tahu dan semoga kuasai.

Masalah SSSP memiliki beberapa algoritma-algoritma berbeda yang efisien (dalam waktu polinomial) (seperti Bellman Ford, BFS, DFS, Dijkstra - 2 Versi, dan/atau Pemrograman Dinamis) yang dapat digunakan berdasarkan sifat dari graf masukan terarah dan berbobot tersebut, misalkan berbobot/tidak berbobot, dengan/tanpa siklus/sisi berbobot negatif, atau secara struktur spesial (sebuah Pohon/sebuah DAG).

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

X Esc
Berikut PgDn

SSSP adalah salah satu masalah graf yang paling sering dijumpai di kehidupan nyata. Setiap kali kita mau berpindah dari satu tempat (biasanya posisi kita sekarang) ke tempat lain (tujuan kita), kita akan berusaha untuk memilih jalur yang pendek — kalau bisa yang terpendek.


Algoritma(-algoritma) SSSP tertanam didalam perangkat lunak peta seperti Google Maps dan didalam berbagai alat Global Positioning System (GPS).


Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.

X Esc
Sebelum PgUp
Berikut PgDn

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 sV.


Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

X Esc
Sebelum PgUp
Berikut PgDn

Tujuan dari masalah SSSP adalah untuk menemukan bobot jalur terpendek dari s ke setiap simpul uV, 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.

X Esc
Sebelum PgUp
Berikut PgDn

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 109)
    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
X Esc
Sebelum PgUp
Berikut PgDn

Pada awalnya, D[u] = +∞ (secara praktis, nilai yang besar seperti 109) ∀uV\\{s}, tetapi D[s] = D[0] = 0.
Pada awalnya, p[u] = -1 (untuk mengatakan 'tidak ada pendahulu') ∀uV.


Sekarang klik Dijkstra(0) — tidak perlu pusing dengan detil karena akan dijelaskan nanti — dan tunggu sampai selesai (sekitar 10 detik pada graf kecil ini).


Pada akhir algoritma SSSP, D[s] = D[0] = 0 (tidak berubah) dan D[u] = δ(s, u)uV
yaitu D[2] = 6, D[4] = 7 (nilai ini disimpan sebagai teks merah dibawah setiap simpul).
Pada akhir algoritma SSSP, p[s] = p[0] = -1 (sumber tidak mempunyai pendahulu), tetapi p[v] = permulaan dari sisi-sisi oranye untuk sisanya, yaitu p[2] = 0, p[4] = 2.


Oleh karena itu, jika kita ada di s = 0 dan mau pergi ke simpul 4, kita akan menggunakan jalur terpendek 0 → 2 → 4 dengan bobot jalur 7.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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: relax operation example

X Esc
Sebelum PgUp
Berikut PgDn

Ada dua sumber berbeda untuk menggambar graf masukan:

  1. Gambar Graf: Anda dapat menggambar graf terarah berbobot apa saja sebagai graf masukan.
  2. Graf-Graf Contoh: Anda dapat memilih dari daftar graf-grafa contoh yang kami sediakan sebagai titik permulaan. Graf-Graf contoh ini mempunyai karakteristik-karakteristik yang berbeda.
X Esc
Sebelum PgUp
Berikut PgDn

In this visualization, we will discuss 6 (SIX) SSSP algorithms.


We will start with the O(V×E) Bellman-Ford algorithm first as it is the most versatile (but also the slowest) SSSP algorithm. We will then discuss 5 (FIVE) other algorithms (including two variants of Dijkstra's algorithm) that solve special-cases of SSSP problem in a much faster manner.

X Esc
Sebelum PgUp
Berikut PgDn

The general purpose Bellman-Ford algorithm can solve all kinds of valid SSSP problem variants (expect one — the one that is ill-defined anyway, to be discussed soon), albeit with a rather slow O(V×E) running time. It also has an extremely simple pseudo-code:

for i = 1 to |V|-1 // O(V) here, so O(V×E×1) = O(V×E)
for each edge(u, v) ∈ E // O(E) here, e.g. by using an Edge List
relax(u, v, w(u, v)) // O(1) here

Without further ado, let's see a preview of how it works on the example graph above by clicking BellmanFord(0) (≈30s, and for now, please ignore the additional loop at the bottom of the pseudo-code).

X Esc
Sebelum PgUp
Berikut PgDn

Bellman-Ford algorithm can be made to run slightly faster on normal input graph, from the worst case of O(V×E) to just O(k×E) where k is the number of iterations of the outer loop of Bellman-Ford.


Discussion: How to do this? Is the speed-up significant?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

To convince the worldwide audience that Bellman-Ford algorithm works, let's temporarily move from visualization mode to proof mode for a few slides.


Theorem 1: If G = (V, E) contains no negative weight cycle, then the shortest path p from source vertex s to a vertex v must be a simple path.


Recall: A simple path is a path p = {v0, v1, v2, ..., vk}, (vi, vi+1) ∈ E, ∀ 0 ≤ i ≤ (k-1) and there is no repeated vertex along this path.

X Esc
Sebelum PgUp
Berikut PgDn
  1. Suppose the shortest path p is not a simple path
  2. Then p must contains one (or more) cycle(s) (by definition of non-simple path)
  3. Suppose there is a cycle c in p with positive weight (e.g., greenbluegreen on the left image) cycle
  4. If we remove c from p, then we will have a shorter 'shortest path' than our shortest path p
  5. A glaring contradiction, so p must be a simple path
X Esc
Sebelum PgUp
Berikut PgDn
  1. Even if c is actually a cycle with zero (0) total weight — it is possible according to our Theorem 1 assumption: no negative weight cycle (see the same greenbluegreen but on the right image), we can still remove c from p without increasing the shortest path weight of p cycle
  2. In conclusion, p is a simple path (from point 5) or can always be made into a simple path (from point 6)

In another word, shortest path p has at most |V|-1 edges from the source vertex s to the 'furthest possible' vertex v in G (in terms of number of edges in the shortest path — see the Bellman-Ford Killer example above).

X Esc
Sebelum PgUp
Berikut PgDn

Theorem 2: If G = (V, E) contains no negative weight cycle, then after Bellman-Ford algorithm terminates, we will have D[u] = δ(s, u), ∀ uV.


For this, we will use Proof by Induction and here are the starting points:


Consider the shortest path p from source vertex s to vertex vi where vi is defined as a vertex which the actual shortest path to reach it requires i hops (edges) from source vertex s. Recall from Theorem 1 that p will be simple path as we have the same assumption of no negative weight cycle.

X Esc
Sebelum PgUp
Berikut PgDn
  1. Initially, D[v0] = δ(s, v0) = 0, as v0 is just the source vertex s
  2. After 1 pass through E, we have D[v1] = δ(s, v1)
  3. After 2 pass through E, we have D[v2] = δ(s, v2)
  4. ...
  5. After k pass through E, we have D[vk] = δ(s, vk)
  6. When there is no negative weight cycle, the shortest path p is a simple path (see Theorem 1), thus the last iteration should be iteration |V|-1
  7. After |V|-1 pass through E, we have D[v|V|-1] = δ(s, v|V|-1), regardless the ordering of edges in E — see the Bellman-Ford Killer example above
X Esc
Sebelum PgUp
Berikut PgDn

Try running BellmanFord(0) on the 'Bellman-Ford Killer' example above. There are V = 7 vertices and E = 6 edges but the edge list E is configured to be at its worst possible order. Notice that after (V-1)×E = (7-1)*6 = 36 operations (~40s, be patient), Bellman-Ford will terminate with the correct answer and there is no way we can terminate Bellman-Ford algorithm earlier.

X Esc
Sebelum PgUp
Berikut PgDn

The only input graph that Bellman-Ford algorithm has issue is the input graph with negative weight cycle reachable from the source vertex s.


However, Bellman-Ford can be used to detect if the input graph contains at least one negative weight cycle reachable from the source vertex s by using the corollary of Theorem 2: If at least one value D[u] fails to converge after |V|-1 passes, then there exists a negative-weight cycle reachable from the source vertex s.


Now run BellmanFord(0) on the example graph that contains negative edges and a negative weight cycle. Please concentrate on the loop at the bottom of the pseudo-code.

X Esc
Sebelum PgUp
Berikut PgDn

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)
X Esc
Sebelum PgUp
Berikut PgDn

Algoritma O(V+E) Breadth-First-Search (BFS) dapat menyelesaikan kasus spesial dari masalah SSSP, yaitu ketika graf masukannya tidak berbobot (seluruh sisi memiliki bobot 1, coba BFS(5) pada contoh 'CP3 4.3' diatas) atau berbobot konstan positif (semua sisi memiliki bobot konstan yang sama, yaitu anda dapat mengubah semua bobot-bobot sisi dari graf contoh diatas dengan bobot konstan positif pilihan anda).

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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) ∀uV\\{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
X Esc
Sebelum PgUp
Berikut PgDn

However, BFS will very likely produce wrong answer when run on weighted graphs as BFS is not actually designed for to solve the weighted version of SSSP problem. There may be a case that taking a path with more number of edges used produces lower total overall path weight than taking a path with minimum number of edges used — which is the output of BFS algorithm.


In this visualization, we will allow you to run BFS even on 'wrong' input graph for pedagogical purpose, but we will display a warning message at the end of the algorithm. For example, try BFS(0) on the general graph above and you will see that vertices {3,4} will have wrong D[3] and D[4] values (and also p[3] and p[4] values).


We will soon see Dijkstra's algorithm (2 implementation variants) for solving certain weighted SSSP problems in a faster way than the general Bellman-Ford algorithm.

X Esc
Sebelum PgUp
Berikut PgDn
Algoritma O((V+E) log V) Dijkstra orisinal adalah algoritma SSSP yang paling sering digunakan untuk input yang khas: Sebuah graf berbobot dan berarah yang tidak memiliki edge berbobot negatif sama sekali (yang biasanya ditemukan dalam kehidupan nyata, coba Graf Contoh: CP3 4.17, Pembunuh Algoritma Bellman Ford, DAG).

Ketika input memiliki edge berbobot negatif, Dijkstra versi original dapat menghasilkan jawaban yang salah (coba Contoh: CP3 4.18, Pembunuh Algoritma Dijkstra).

Algoritma Dijkstra dapat juga diimplementasikan dengan cara berbeda. Algoritma O((V+E) log VDijkstra modifikasi dapat digunakan untuk graf berbobot dan berarah yang memiliki edge berbobot negatif, namun tidak memiliki siklus berbobot negatif (coba Contoh: CP3 4.18, namun sangatlah lambat pada Pembunuh Algoritma Dijkstra). Algoritma ini juga akan terperangkap dalam pengulangan tak hingga untuk graf berarah dan berbobot yang memiliki setidaknya satu siklus berbobot negatif yang dapat dijangkau dari simpul sumber (coba Contoh: CP3 4.19).
X Esc
Sebelum PgUp
Berikut PgDn

Dijkstra's algorithm maintains a set S (Solved) of vertices whose final shortest path weights have been determined. Initially S = {s}, the source vertex s only.


Then, it repeatedly selects vertex u in {V\S} with the minimum shortest path estimate, adds u to S, and relaxes all outgoing edges of u. Detailed proof of correctness of this Dijkstra's algorithm is usually written in typical Computer Science algorithm textbooks. For a simpler intuitive visual explanation on why this greedy strategy works, see this.


This entails the use of a Priority Queue as the shortest path estimates keep changing as more edges are processed. The choice of relaxing edges emanating from vertex with the minimum shortest path estimate first is greedy, i.e. use the "best so far", but we will see later that it can be proven that it will eventually ends up with an optimal result — if the graph has no negative weight edge.

X Esc
Sebelum PgUp
Berikut PgDn

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).

X Esc
Sebelum PgUp
Berikut PgDn

Every time a vertex is processed, we relax its neighbors. In total, E edges are processed.


If by relaxing edge(u, v), we have to decrease D[v], we call the O(log V) DecreaseKey() operation in Binary Min Heap (harder to implement as C++ STL priority_queue/Python heapq/Java PriorityQueue does not support this operation efficiently yet) or simply delete the old entry and then re-insert a new entry in balanced BST like AVL Tree (which also runs in O(log V), but this is much easier to implement, just use C++ STL set/Java TreeSet — unfortunately not natively supported in Python).


Therefore, this part is O(E log V).


Thus in overall, Dijkstra's algorithm runs in O(V log V + E log V) = O((V+E) log V) time, which is much faster than the O(V×E) Bellman-Ford algorithm.

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Ketika graf masukan memiliki setidaknya satu sisi berbobot negatif — tidak harus siklus berbobot negatif — algoritma Dijkstra bisa menghasilkan jawaban yang salah.


Cobalah Dijkstra(0) pada salah satu dari Graf-Graf Contoh: CP3 4.18.


Pada akhir eksekusi dari algoritma Dijkstra, simpul 4 memiliki nilai D[4] yang salah karena algoritmanya 'salah' pada awalnya berpikir bahwa sub-jalur 0 → 1 → 3 adalah sub-jalur yang lebih baik dengan bobot 1+2 = 3, oleh karenanya membuat D[4] = 6 setelah memanggil relax(3,4,3). Tetapi, keberadaan bobot negatif -10 pada sisi 2 → 3 membuat sub-jalur yang lain 0 → 2 → 3 pada akhirnya adalah sub-jalur yang lebih baik dengan bobot 10-10 = 0 meskipun sub-jalur ini mulai dengan lebih jelek karena bobot jalurnya 10 setelah sisi pertama 0 → 2. Nilai D[3] = 0 yang lebih baik tidak pernah disebarkan lebih lanjut karena natur rakus (greedy) dari algoritma Dijkstra, oleh karenanya D[4] menjadi salah.

X Esc
Sebelum PgUp
Berikut PgDn

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: CP3 4.18 that has troubled the original version of Dijkstra's algorithm (see previous slide).

X Esc
Sebelum PgUp
Berikut PgDn

The key idea is the 'usage modification' done to C++ STL priority_queue/Python heapq/Java PriorityQueue to allow it to perform the required 'DecreaseKey' operation efficiently, i.e., in O(log V) time.


The technique is called 'Lazy Update' where we leave the 'outdated/weaker/bigger-valued information' in the Min Priority Queue instead of deleting it straight-away. As the items are ordered from smaller values to bigger values in a Min PQ, we are guaranteeing ourself that we will encounter the smallest/most-up-to-date item first before encountering the weaker/outdated item(s) later - which by then can be easily ignored.

X Esc
Sebelum PgUp
Berikut PgDn

On non-negative weighted graphs, the behavior of Modified Dijkstra's implementation is exactly the same as the Original Dijkstra's so we can use the same time complexity analysis of O((V+E) log V).


PS: We note that when we use the Modified Dijkstra's algorithm, there can be more items (up to E) in the Priority Queue than if we use the Original Dijkstra's algorithm (up to V). However, since O(log E) = O(log V^2) = O(2 log V) = O(log V), we still treat the Priority Queue operations as O(log V).


However, if the graph has at least one negative weight edge, the analysis is harder.

X Esc
Sebelum PgUp
Berikut PgDn

Ketika graf masukan memiliki setidaknya satu sisi berbobot negatif tetapi tidak ada siklus berbobot negatif — algoritma Dijkstra termodifikasi menghasilkan jawaban yang benar.


Cobalah ModifiedDijkstra(0) pada satu dari Graf-Graf Contoh: CP3 4.18 yang menyebabkan masalah untuk Dijkstra(0).


Pada akhir dari eksekusi algoritma ModifiedDijkstra, simpul 4 memiliki nilai D[4] yang benar karena meskipun algoritma Dijkstra termodifikasi juga mulai dengan 'salah' dengan menganggap sub-jalur 0 → 1 → 3 adalah sub-jalur yang lebih baik dengan bobot 1+2 = 3, sehingga membuat D[4] = 6 setelah memanggil relax(3,4,3). Disini, algoritma Dijkstra termodifikasi terus menyebarkan D[3] = 0 setelah algoritma ini menemukan bahwa sub-jalur lain 0 → 2 → 3 sebenarnya adalah sub-jalur yang lebih baik dengan bobot 10-10 = 0. Maka D[4] akhirnya benar kembali. Tetapi, algoritma ini ada kemungkinan menjalankan (jauh lebih banyak) operasi daripada O((V+E) log V).

X Esc
Sebelum PgUp
Berikut PgDn

Sayangnya, menjalankan ModifiedDijkstra(0) pada graf dengan siklus berbobot negatif seperti yang ditunjukkan pada salah satu Graf-Graf Contoh: CP3 4.17 diatas akan menyebabkan loop yang tidak berakhir (animasinya sangat panjang tetapi kami membatasi jumlah loop sebesar 100 sisi-sisi yang diproses supaya web browser anda tidak hang).

X Esc
Sebelum PgUp
Berikut PgDn

Try ModifiedDijkstra(0) on the extreme corner case above that is very hard to derive without proper understanding of this algorithm and was part of Asia Pacific Informatics Olympiad (APIO) 2013 task set by Steven.


The Modified Dijkstra's algorithm will terminate with correct answer, but only after running exponential number of operations (each carefully constructed triangle raises the number of required operations by another power of two). Thus we cannot prematurely terminate Modified Dijkstra's in this worst case input situation.


However, such extreme corner case is rare and thus in practice, Modified Dijkstra's algorithm can be used on directed graphs that have some negative weighted edges as long as the graph has no negative weight cycle reachable from the source vertex s.

X Esc
Sebelum PgUp
Berikut PgDn

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 uV 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)?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.


Contohnya, coba DP(0) pada contoh DAG diatas. Pertama-tama, algoritma ini menghitung satu (ada yang lain) kemungkinan urutan topologis dengan menggunakan O(V+E) DFS atau BFS/algoritma Kahn yang dijelaskan di modul Penjelajahan Graf. Contohnya, misalkan satu urutan topologis adalah {0,2,1,3,4,5}. Maka, algoritma ini akan merelaksasi sisi-sisi keluar dari simpul-simpul yang terdaftar di urutan topologis tersebut. Setelah dalam satu O(V+E) iterasi, kita akan mendapatkan nilai-nilai D[u] yang benar ∀uV.
X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

Algoritma DP untuk menyelesaikan SSSP pada DAG juga disebut sebagai algoritma Bellman Ford satu-pass 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.

X Esc
Sebelum PgUp
Berikut PgDn

We have lots of other stuffs on top of this basic explanation of SSSP algorithms for SSSP problems.


Meanwhile, you are allowed to use/modify our implementation code for Bellman-Ford/Bellman-Ford-Moore/Dijkstra's Algorithms:
bellman_ford.cpp/bellman_ford_moore.cpp/dijkstra.cpp
bellman_ford.java/bellman_ford_moore.java/dijkstra.java
bellman_ford.py/bellman_ford_moore.py/dijkstra.py
bellman_ford.ml/bellman_ford_moore.ml/dijkstra.ml

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn
Selagi aksi dijalankan, tiap langkahnya akan dijelaskan pada panel status.
X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn
Kendalikan animasi dengan tombol kendali! Terdapat pula shortcut melalui keyboard:
Spasi: play/pause/replay
Panah kanan/kiri: maju ke depan/belakang
-/+: turunkan/tingkatkan kecepatan

X Esc
Sebelum PgUp
Berikut PgDn
Kembali ke 'Mode Eksplorasi' untuk memulai eksplorasi!

Harap diingat bahwa jika anda menemukan bug pada visualisasi ini atau bila anda ingin meminta fitur / visualisasi baru, jangan segan-segan untuk menghubungi pemimpin proyek ini: Dr Steven Halim melalui alamat emailnya: stevenhalim at gmail dot com.
X Esc
Sebelum PgUp

Gambar Grafik

Contoh Graf

Algoritma Bellman Ford(s)

Algoritma BFS(s)

Algoritma Dijkstra(s)

Algoritma DFS(s)

Pemrograman Dinamis(s)

>

CP3 4.3 U/U

CP3 4.4 D/U

CP3 4.17 D/W

CP3 4.18 -ve weight

CP3 4.19 -ve cycle

CP3 4.40 Tree

Bellman Ford's Killer

Dijkstra's Killer

DAG

s =

Lakukan

s =

Lakukan

s =

Original

Telah dimodifikasi

s =

Lakukan

s =

Lakukan

Tentang Tim Syarat Guna

Tentang

VisuAlgo digagas pada tahun 2011 oleh Dr Steven Halim sebagai alat untuk membantu murid-muridnya mengerti struktur data dan algoritma dengan memampukan mereka untuk mempelajari dasar-dasar struktur data dan algoritma secara otodidak dan dengan kecepatan mereka sendiri.


VisuAlgo mempunya banyak algoritma-algoritma tingkat lanjut yang dibahas didalam buku Dr Steven Halim ('Competitive Programming', yang ditulis bersama adiknya Dr Felix Halim) dan lebih lagi. Hari ini, beberapa dari visualisasi/animasi algoritma-algoritma tingkat lanjut ini hanya ditemukan di VisuAlgo.


Meskipun pada khususnya didesain untuk murid-murid National University of Singapore (NUS) yang mengambil berbagai kelas-kelas struktur data dan algoritma (contoh: CS1010, CS1020, CS2010, CS2020, CS3230, dan CS3233), sebagai pendukung pembelajaran online, kami berharap bahwa orang-orang di berbagai belahan dunia menemukan visualisasi-visualisasi di website ini berguna bagi mereka juga.


VisuAlgo tidak didesain untuk layar sentuh kecil (seperti smartphones) dari awalnya karena kami harus membuat banyak visualisasi-visualisasi algoritma kompleks yang membutuhkan banyak pixels dan gestur klik-dan-tarik untuk interaksinya. Resolusi layar minimum untuk pengalaman pengguna yang lumayan adalah 1024x768 dan hanya halaman utama VisuAlgo yang secara relatif lebih ramah dengan layar kecil.


VisuAlgo adalah proyek yang sedang terus berlangsung dan visualisasi-visualisasi yang lebih kompleks sedang dibuat.


Perkembangan yang paling menarik adalah pembuatan pertanyaan otomatis (sistem kuis online) yang bisa dipakai oleh murid-murid untuk menguji pengetahuan mereka tentang dasar-dasar struktur data dan algoritma. Pertanyaan-pertanyaan dibuat secara acak dengan semacam rumus dan jawaban-jawaban murid-murid dinilai secara instan setelah dikirim ke server penilai kami. Sistem kuis online ini, saat sudah diadopsi oleh banyak dosen Ilmu Komputer diseluruh dunia, seharusnya bisa menghapuskan pertanyaan-pertanyaan dasar tentang struktur data dan algoritma dari ujian-ujian di banyak Universitas. Dengan memberikan bobot kecil (tapi tidak kosong) supaya murid-murid mengerjakan kuis online ini, seorang dosen Ilmu Komputer dapat dengan signifikan meningkatkan penguasaan materi dari murid-muridnya tentang pertanyaan-pertanyaan dasar ini karena murid-murid mempunyai kesempatan untuk menjawab pertanyaan-pertanyaan ini yang bisa dinilai secara instan sebelum mereka mengambil kuis online yang resmi. Mode latihan saat ini mempunyai pertanyaan-pertanyaan untuk 12 modul visualisasi. Kami akan segera menambahkan pertanyaan-pertanyaan untuk 8 modul visualisasi lainnya sehingga setiap every modul visualisasi di VisuAlgo mempunyai komponen kuis online.


Cabang pengembangan aktif lainnya adalah sub-proyek penerjemahan dari VisuAlgo. Kami mau menyiapkan basis data kosa kata Ilmu Komputer dalam bahasa Inggris yang digunakan di sistem VisuAlgo. Ini adalah pekerjaan besar yang membutuhkan crowdsourcing. Saat sistem tersebut siap, kami akan mengundang beberapa dari anda untuk berkontribusi, terutama bila bahasa Inggris bukan bahasa ibu anda. Saat ini, kami juga telah menulis catatan-catatan publik tentang VisuAlgo dalam berbagai bahasa:
zh, id, kr, vn, th.

Tim

Pemimpin & Penasihat Proyek (Jul 2011-sekarang)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Murid-Murid S1 Peniliti 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Murid-Murid Proyek Tahun Terakhir/UROP 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Murid-Murid Proyek Tahun Terakhir/UROP 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Murid-Murid S1 Peniliti 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Murid-Murid Proyek Tahun Terakhir/UROP 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Murid-Murid Proyek Tahun Terakhir/UROP 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

List of translators who have contributed ≥100 translations can be found at statistics page.

Ucapan Terima Kasih
Proyek ini dimungkinkan karena Hibah Pengembangan Pengajaran dari NUS Centre for Development of Teaching and Learning (CDTL).

Syarat Guna

VisuAlgo bebas biaya untuk komunitas Ilmu Komputer di dunia. Jika anda menyukai VisuAlgo, satu-satunya pembayaran yang kami minta dari anda adalah agar anda menceritakan keberadaan VisuAlgo kepada murid-murid/dosen-dosen Ilmu Komputer yang anda tahu =) lewat Facebook, Twitter, situs mata kuliah, ulasan di blog, email, dsb.


Jika anda adalah murid/dosen struktur data dan algoritma, anda diijinkan untuk menggunakan situs ini secara langsung di kelas-kelas anda. Jika anda mengambil screen shots (video-video) dari situs ini, anda dapat menggunakan screen shots (video-video) tersebut ditempat lain asalkan anda menyebut URL dari situs ini (http://visualgo.net) dan/atau daftar publikasi dibawah ini sebagai referensi. Tetapi, anda TIDAK diijinkan untuk mengunduh berkas-berkas VisuAlgo (sisi-klien) dan memasangnya di situs anda sendiri karena itu dikategorikan sebagai plagiat. Saat ini, kami TIDAK mengijinkan orang lain untuk membuat cabang/varian dari proyek VisuAlgo ini. Menggunakan kopi offline (sisi-klien) dari VisuAlgo untuk kepentingan pribadi diijinkan.


Ingat bahwa komponen kuis online dari VisuAlgo secara natur membutuhkan sisi-server dan tidak bisa dengan mudah disimpan di komputer lokal. Saat ini, publik hanya bisa menggunkaan 'mode latihan' untuk mengakses sistem kuis online. Saat ini, 'mode ujian' adalah sistem untuk mengakses pertanyaan-pertanyaan acak ini yang digunakan untuk ujian resmi di NUS. Dosen-dosen Ilmu Komputer yang lain harus menghubungi Steven jika anda mau mencoba 'mode ujian' tersebut.


Dafatar Publikasi


Karya ini telah dipresentasikan singkat pada CLI Workshop sewaktu ACM ICPC World Finals 2012 (Poland, Warsaw) dan pada IOI Conference di IOI 2012 (Sirmione-Montichiari, Italy). Anda bisa mengklik link ini untuk membaca makalah kami tahun 2012 tentang sistem ini (yang belum disebut sebagai VisuAlgo pada tahun 2012 tersebut).


Karya ini dibuat denbgan bantuan bekas murid-murid saya. Laporan-laporan proyek yang cukup mutakhir bisa dibaca disini: Erin, Wang Zi, Rose, Ivan.


Laporan Bug atau Meminta Fitur Baru


VisuAlgo bukanlah proyek yang sudah selesai. Dr Steven Halim masih aktif dalam mengembangkan VisuAlgo. Jika anda adalah pengguna VisuAlgo dan menemukan bug di halaman visualisasi/sistem kuis online atau jika anda mau meminta fitur baru, silahkan hubungi Dr Steven Halim. Alamat emailnya adalah gabungan dari namanya dan tambahkan gmail titik com.