Kalkulator Jalur Terpendek Dijkstra

Selamat datang di Kalkulator Jalur Terpendek Dijkstra, alat interaktif untuk menemukan jalur terpendek dalam graf berbobot menggunakan algoritma Dijkstra. Baik Anda seorang mahasiswa ilmu komputer yang sedang mempelajari teori graf, profesional jaringan yang menganalisis protokol perutean, atau pengembang yang mengimplementasikan pencarian jalur, kalkulator ini menyediakan eksplorasi visual langkah demi langkah dari salah satu algoritma paling mendasar dalam ilmu komputer.

Apa itu Algoritma Dijkstra?

Algoritma Dijkstra, ditemukan oleh ilmuwan komputer Belanda Edsger W. Dijkstra pada tahun 1956, adalah algoritma pencarian graf yang memecahkan masalah jalur terpendek sumber tunggal untuk graf berbobot dengan bobot tepi non-negatif. Diberikan simpul sumber, algoritma ini menemukan jalur terpendek dari simpul tersebut ke setiap simpul lain dalam graf.

Algoritma ini bekerja dengan memelihara sekumpulan simpul yang belum dikunjungi dan berulang kali memilih simpul yang belum dikunjungi dengan jarak tentatif terkecil (strategi rakus). Inilah yang membuatnya elegan dan efisien — begitu sebuah simpul "dikunjungi", jarak terpendeknya dijamin final.

Pseudocode Algoritma

Formula Inti

Di mana:

• d[u] = jarak terpendek saat ini yang diketahui dari sumber ke simpul u
• w(u, v) = bobot tepi dari u ke v
• d[v] = jarak terpendek saat ini yang diketahui dari sumber ke simpul v

Cara Menggunakan Kalkulator Ini

1. Tentukan tepi graf Anda: Masukkan tepi dalam format sumber, tujuan, bobot, satu per baris. Setiap baris mewakili koneksi antara dua simpul.
2. Pilih jenis graf: Pilih "Tidak Berarah" untuk tepi dua arah (seperti jalan raya) atau "Berarah" untuk tepi satu arah (seperti rute penerbangan atau tautan web).
3. Atur simpul sumber: Masukkan simpul awal dari mana semua jalur terpendek akan dihitung.
4. Cari jalur terpendek: Klik tombol untuk menjalankan algoritma Dijkstra. Jelajahi visualisasi graf interaktif, tabel jarak, dan pelacakan langkah demi langkah.
5. Telusuri langkah-langkah: Gunakan tombol Berikutnya/Sebelumnya untuk melihat algoritma dieksekusi satu langkah pada satu waktu, dengan graf yang menyoroti simpul dan tepi yang diperbarui secara real-time.

Memahami Hasil

Tabel Jarak

Menunjukkan jarak terpendek dari sumber ke setiap simpul, beserta jalur lengkapnya. Simpul yang ditandai ∞ tidak dapat dijangkau dari sumber.

Visualisasi Graf

Canvas interaktif menunjukkan graf Anda dengan simpul dan tepi berkode warna:

• Simpul biru = Simpul sumber
• Simpul hijau = Dikunjungi (jarak final)
• Simpul oranye = Sedang diproses
• Simpul abu-abu = Belum dikunjungi
• Tepi hijau = Pohon jalur terpendek

Pelacakan Langkah demi Langkah

Menunjukkan eksekusi algoritma termasuk ekstraksi antrean prioritas, relaksasi tepi, dan pembaruan jarak pada setiap langkah. Ini sangat berharga untuk mempelajari cara kerja algoritma.

Kompleksitas Waktu

Efisiensi algoritma Dijkstra bergantung pada struktur data yang digunakan untuk antrean prioritas:

Di mana V adalah jumlah verteks (simpul) dan E adalah jumlah tepi. Kalkulator ini menggunakan implementasi binary heap.

Graf Berarah vs. Tidak Berarah

• Graf tidak berarah: Tepi antara A dan B berarti Anda dapat melakukan perjalanan A→B dan B→A. Contoh: jaringan jalan, jaringan pertemanan, sirkuit listrik.
• Graf berarah: Tepi dari A ke B hanya memungkinkan perjalanan A→B, tidak selalu B→A. Contoh: hyperlink web, pengikut Twitter, rute penerbangan, aliran sungai.

Batasan Algoritma Dijkstra

• Tidak ada bobot negatif: Algoritma Dijkstra menghasilkan hasil yang salah dengan bobot tepi negatif. Gunakan Bellman-Ford untuk graf dengan bobot negatif (tetapi tanpa siklus negatif).
• Sumber tunggal: Ini menemukan jalur terpendek dari satu sumber. Untuk jalur terpendek semua-pasangan, gunakan Floyd-Warshall atau jalankan Dijkstra dari setiap simpul.
• Tidak ada siklus negatif: Siklus negatif membuat jalur terpendek tidak terdefinisi (Anda selalu dapat mengelilingi siklus untuk mengurangi jarak tanpa batas).

Aplikasi Dunia Nyata

Navigasi GPS

Layanan pemetaan menggunakan varian algoritma Dijkstra (seringkali dengan heuristik A*) untuk menemukan rute tercepat antara dua lokasi. Persimpangan jalan adalah simpul, dan segmen jalan adalah tepi berbobot (berdasarkan waktu atau jarak).

Perutean Jaringan

Protokol perutean internet seperti OSPF (Open Shortest Path First) dan IS-IS menggunakan algoritma Dijkstra untuk menghitung jalur terpendek melalui topologi jaringan. Setiap router membangun pohon jalur terpendek untuk menentukan penerusan paket.

Analisis Jejaring Sosial

Menemukan jalur koneksi terpendek antar pengguna (derajat pemisahan), menghitung ukuran sentralitas, dan mengidentifikasi simpul yang berpengaruh dalam jaringan.

Pengembangan Game

Pencarian jalur NPC dalam video game menggunakan algoritma Dijkstra atau A* (yang memperluas Dijkstra dengan heuristik) untuk menavigasi peta game dan menemukan jalur pergerakan yang optimal.

Rantai Pasokan & Logistik

Mengoptimalkan rute pengiriman, jalur gudang-ke-toko, dan jaringan transportasi multi-moda di mana metode transportasi yang berbeda memiliki biaya yang berbeda.

Pertanyaan yang Sering Diajukan

Apa itu algoritma Dijkstra?

Algoritma Dijkstra adalah algoritma pencarian graf yang menemukan jalur terpendek dari simpul sumber ke semua simpul lainnya dalam graf berbobot dengan bobot tepi non-negatif. Ia menggunakan strategi rakus dengan antrean prioritas (min-heap), selalu memproses simpul yang belum dikunjungi dengan jarak terkecil yang diketahui. Kompleksitas waktunya adalah O((V + E) log V) dengan binary heap.

Dapatkah algoritma Dijkstra menangani bobot tepi negatif?

Tidak, algoritma Dijkstra mengharuskan semua bobot tepi bernilai non-negatif. Bobot negatif dapat menyebabkan algoritma menghasilkan hasil yang salah karena begitu sebuah simpul ditandai sebagai dikunjungi, jaraknya dianggap final. Untuk graf dengan bobot negatif (tetapi tanpa siklus negatif), gunakan algoritma Bellman-Ford sebagai gantinya.

Apa perbedaan antara graf berarah dan tidak berarah?

Dalam graf berarah, tepi memiliki arah — tepi dari A ke B tidak berarti ada tepi dari B ke A. Dalam graf tidak berarah, tepi bekerja dua arah — jika ada koneksi antara A dan B, Anda dapat melakukan perjalanan ke salah satu arah. Jaringan jalan biasanya dimodelkan sebagai graf tidak berarah, sedangkan tautan web dan rute penerbangan adalah berarah.

Apa itu relaksasi tepi dalam algoritma Dijkstra?

Relaksasi tepi adalah operasi inti dalam algoritma Dijkstra. Saat mengunjungi simpul u, untuk setiap tetangga v, algoritma memeriksa apakah jalur melalui u (dist[u] + weight(u,v)) lebih pendek dari jarak yang diketahui saat ini ke v (dist[v]). Jika lebih pendek, jarak diperbarui (direlaksasi) dan v ditambahkan ke antrean prioritas dengan jarak baru.

Apa itu pohon jalur terpendek?

Pohon jalur terpendek (SPT) adalah subgraf yang berakar pada simpul sumber yang berisi jalur terpendek dari sumber ke semua simpul yang dapat dijangkau. Setiap simpul (kecuali sumber) memiliki tepat satu induk — pendahulu pada jalur terpendeknya. SPT adalah produk sampingan dari algoritma Dijkstra dan berguna untuk perutean dan desain jaringan.

Apa saja aplikasi dunia nyata dari algoritma Dijkstra?

Algoritma Dijkstra digunakan dalam sistem navigasi GPS, protokol perutean jaringan (OSPF, IS-IS), analisis jejaring sosial, optimasi rute maskapai penerbangan, perencanaan jalur robot, pencarian jalur AI dalam game, logistik rantai pasokan, dan desain jaringan telekomunikasi. Masalah apa pun yang dapat dimodelkan sebagai pencarian jalur terpendek atau biaya terendah dalam graf mendapat manfaat dari algoritma ini.

Sumber Daya Tambahan

• Algoritma Dijkstra - Wikipedia
• Masalah Jalur Terpendek - Wikipedia
• Teori Graf - Wikipedia