>

>
1x
go to beginning previous frame pause play next frame go to end

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


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.
If you are an NUS student and a repeat visitor, please login.

🕑

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 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

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.


Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). 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.

🕑

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.


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

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
🕑

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.

🕑

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

🕑

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-graf contoh yang kami sediakan sebagai titik permulaan. Graf-Graf contoh ini mempunyai karakteristik-karakteristik yang berbeda.
🕑

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?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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 = {v0, v1, v2, ..., vk}, (vi, vi+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 hijaubiruhijau pada gambar di sisi kiri) cycle
  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
🕑
  1. 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 hijaubiruhijau yang sama tetapi pada gambar di sisi kanan), kita tetap bisa menghapus c dari p tanpa menambah bobot jalur terpendek dari p cycle
  2. 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), ∀ uV.


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 vi dimana vi 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[v0] = δ(s, v0) = 0, karena v0 adalah simpul sumber s
  2. Setelah 1 pass melalui E, kita punya D[v1] = δ(s, v1)
  3. Setelah 2 pass melalui E, kita punya D[v2] = δ(s, v2)
  4. ...
  5. Setelah k pass melalui E, kita punya D[vk] = δ(s, vk)
  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)
🕑

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

🕑

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) ∀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
🕑

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.

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

Algoritma Dijkstra menjaga sebuah set S (Solved/terselesaikan) dari simpul-simpul yang dimana bobot-bobot jalur terpendek finalnya sudah ditentukan. Pada awalnya S = {s}, simpul sumber s saja.


Lalu, algoritma ini secara berulang memilih simpul u dalam {V\\S} dengan estimasi jalur terpendek minimum, menambahkan u ke S, 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.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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.

🕑

Algoritma Dijkstra juga bisa diimplementasikan dengan berbeda. Algoritma O((V+E) log V) Dijkstra termodifikasi bisa digunakan untuk graf-graf terarah berbobot yang mungkin memiliki sisi-sisi berbobot negatif tetapi tidak ada siklus berbobot negatif.


Graf masukan seperti itu terdapat pada beberapa kasus-kasus praktis, misalkan bepergian dengan mobil elektrik yang memiliki batere dan tujuan kita adalah untuk menemukan jalur dari simpul sumber s ke simpul lain yang meminimalkan penggunaan batere secara umum. Seperti biasa, pada akselerasi (atau menyetir di jalan yang rata/menaik), mobil elektrik menggunakan energi (positif) dari batere. Tetapi, pada pengereman (atau menyeter pada jalan menurun), mobil elektrik mengisi ulang energi (atau menggunakan energi negatif) ke batere. Tidak ada siklus berbobot negatif karena hilangnya energi kinetik.


Contohnya, cobalah ModifiedDijkstra(0) pada salah satu dari Graf-Graf Contoh: CP3 4.18 yang telah membuat algoritma Dijkstra versi asli bermasalah (lihat slide sebelumnya).

🕑

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.

🕑

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

🕑

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

🕑

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


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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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.


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

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.


Sementara itu, anda diijinkan untuk menggunakan/memodifikasi kode implementasi kami untuk algoritma-algoritma Bellman-Ford/Bellman-Ford-Moore/Dijkstra: 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
🕑

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.


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

Gambar Grafik

Graf-Graf Contoh

BellmanFord(s)

BFS(s)

Dijkstra(s)

DFS(s)

PD(s)

>

Unweighted

Weighted

Negative Weight

Corner Case

Special Case

s =

Lakukan

s =

Lakukan

s =

Original

Telah dimodifikasi

s =

Lakukan

s =

Lakukan

We use cookies to improve our website.
By clicking ACCEPT, you agree to our use of Google Analytics for analysing user behaviour and improving user experience as described in our Privacy Policy.
By clicking reject, only cookies necessary for site functions will be used.

ACCEPT REJECT
Tentang Tim Syarat Guna Kebijakan Privasi

Tentang

VisuAlgo digagas pada tahun 2011 oleh Dr Steven Halim sebagai alat untuk membantu murid-muridnya mengerti struktur-struktur data dan algoritma-algoritma, dengan memampukan mereka untuk mempelajari dasar-dasarnya 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 temannya Dr Suhendry Effendy) 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/setara, CS2040/setara, CS3230, CS3233, dan CS4234), 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. Tetapi, kami sedang bereksperimen dengan versi mobil (kecil) dari VisuAlgo yang akan siap pada April 2022.


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 struktur-struktur data dan algoritma-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 12 modul visualisasi yang lainnya sehingga setiap setiap modul visualisasi di VisuAlgo mempunyai komponen kuis online.


Kami telah menerjemahkan halaman-halaman VisuALgo ke tiga bahasa-bahasa utama: Inggris, Mandarin, dan Indonesia. Saat ini, kami juga telah menulis catatan-catatan publik tentang VisuAlgo dalam berbagai bahasa:

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, Senior 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

Murid-Murid Proyek Tahun Terakhir/UROP 5 (Aug 2021-Dec 2022)
Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long

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 is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitter/Instagram/TikTok posts, course webpages, blog reviews, emails, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (https://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for real examinations in NUS.

List of Publications

This work has been presented briefly at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

This work is done mostly by my past students. 

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

Kebijakan Privasi

Versi 1.1 (Dimutakhirkan Jum, 14 Jan 2022).

Pemberitahuan kepada semua pengunjung: Kami saat ini menggunakan Google Analytics untuk mendapatkan pengertian garis besar tentang pengunjung-pengunjung situs kami. Kami sekarang memberikan opsi kepada pengguna untuk Menerima atau Menolak pelacak ini.

Sejak Rabu, 22 Des 2021, hanya staff-staff/murid-murid National University of Singapore (NUS) dan dosen-dosen Ilmu Komputer diluar dari NUS yang telah menulis kepada Steven dapat login ke VisuAlgo, orang-orang lain di dunia harus memakai VisuAlgo sebagai pengguna anonim yang tidak benar-benar terlacak selain apa yang dilacak oleh Google Analytics.

Untuk murid-murid NUS yang mengambil mata kuliah yang menggunakan VisuAlgo: Dengan menggunakan akun VisuAlgo (sebuah tupel dari alamat email NUS resmi, nama murid resmi NUS seperti dalam daftar kelas, dan sebuah kata sandi yang dienkripsi pada sisi server — tidak ada data personal lainnya yang disimpan), anda memberikan ijin kepada dosen modul anda untuk melacak pembacaan slide-slide kuliah maya dan kemajuan latihan kuis online yang dibutuhkan untuk menjalankan modul tersebut dengan lancar. Akun VisuAlgo anda akan juga dibutuhkan untuk mengambil kuis-kuis VisuAlgo online resmi sehingga memberikan kredensial akun anda ke orang lain untuk mengerjakan Kuis Online sebagai anda adalah pelanggaran akademis.. Akun pengguna anda akan dihapus setelah modul tersebut selesai kecuali anda memilih untuk menyimpan akun anda (OPT-IN). Akses ke basis data lengkap dari VisuAlgo (dengan kata-kata sandi terenkripsi) dibatasi kepada Steven saja.

Untuk murid-murid NUS lainnya, anda dapat mendaftarkan sendiri sebuah akun VisuAlgo (OPT-IN).

Untuk dosen-dosen Ilmu Komputer di seluruh dunia yang telah menulis kepada Steven, sebuah akun VisuAlgo (alamat email (bukan-NUS), anda dapat menggunakan nama panggilan apapun, dan kata sandi terenkripsi) dibutuhkan untuk membedakan kredensial online anda dibandingkan dengan orang-orang lain di dunia. Akun anda akan dilacak seperti seorang murid NUS biasa diatas tetapi akun anda akan mempunya fitur-fiture spesifik untuk dosen-dosen Ilmu Komputer, yaitu kemampuan untuk melihat slide-slide tersembunyi yang berisi jawaban-jawaban (menarik) dari pertanyaan-pertanyaan yang dipresentasikan di slide-slide sebelumnya sebelum slide-slide tersembunyi tersebut. Anda juga dapat mengakses setingan Susah dari Kuis-Kuis Online VisuAlgo. Anda dapat dengan bebas menggunakan materi-materia untuk memperkaya kelas-kelas struktur-struktur data dan algoritma-algoritma anda. Catatan: Mungkin ada fitur-fitur khusus tambahan untuk dosen Ilmu Komputer di masa mendatang.

Untuk siapapun dengan akun VisuAlgo, anda dapat membuang akun anda sendiri bila anda tidak mau lagi diasosiasikan dengan tool VisuAlgo ini.