Final
Dalam antrean
Sisi diperiksa

  • Saat ini
  • Dalam antrean
  • Final
  • Jalur
Klik pada simpul mengatur

Selengkapnya tentang algoritma Dijkstra

Algoritma Dijkstra

Algoritma Dijkstra mencari rute terpendek dari awal ke setiap simpul lain saat sisi punya panjang, seperti jalan antarkota. Algoritma ini meluas dari awal, selalu mengambil simpul terdekat yang belum selesai. Klik simpul untuk mulai dari sana, pilih tujuan jika mau, lalu jalankan langkah demi langkah untuk melihat antrean, tiap jarak yang turun saat jalan yang lebih pendek muncul, dan jalur terpendek yang terbentuk. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Klik simpul untuk menjadikannya awal; ubah klik ke Tujuan lalu klik simpul lain untuk mencari jalur terpendek ke sana. Angka di tiap sisi adalah panjangnya, angka di tiap simpul adalah jarak terpendeknya sejauh ini, dan baris di bawah graf adalah antrean, yang terdekat lebih dulu. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Klik simpul untuk menjadikannya awal. Untuk mencari jalur, ubah klik ke Tujuan lalu klik simpul lain.
  2. Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
  3. Perhatikan antrean di bawah graf dan jarak di tiap simpul. Graf baru membuat graf lain untuk dicoba.

Cara kerja algoritma Dijkstra

Beri awal jarak 0 dan setiap simpul lain tak hingga, lalu masukkan awal ke antrean. Kemudian ulangi: ambil simpul dalam antrean dengan jarak terkecil, dan tandai jarak itu final. Untuk tiap tetangganya yang belum final, tambahkan panjang sisi ke jarak simpul itu. Jika jumlahnya lebih pendek dari jarak tetangga sejauh ini, jumlah itu menjadi jarak baru, simpul itu diingat sebagai jalan ke sana, dan tetangga masuk ke antrean jika belum ada di dalamnya. Saat antrean kosong, setiap simpul yang bisa dicapai sudah punya jarak terpendeknya.

Mengapa simpul terdekat sudah final

Saat sebuah simpul adalah yang terdekat dalam antrean, setiap jalan lain ke sana harus keluar dari bagian graf yang sudah selesai lewat suatu simpul dalam antrean, yang setidaknya sama jauhnya, lalu menambah sisi yang tidak mungkin negatif. Jadi tidak ada jalan lain yang bisa lebih pendek. Itu juga sebabnya tujuan baru pasti saat diambil dari antrean, bukan saat pertama kali dicapai, dan mengapa algoritma Dijkstra gagal dengan sisi negatif: di situ, algoritma Bellman–Ford diperlukan. Jika setiap sisi panjangnya 1, algoritma Dijkstra bekerja sama seperti Breadth-First Search (BFS).

Pertanyaan yang sering diajukan

Apa itu algoritma Dijkstra?

Cara mencari jalur terpendek dari satu simpul awal ke semua simpul lain di graf yang panjang sisinya nol atau lebih. Algoritma ini berulang kali mengambil simpul terdekat yang belum selesai, membuat jaraknya final, dan memakai sisi-sisinya untuk memperpendek jarak tetangganya.

Mengapa algoritma Dijkstra tidak bisa dipakai dengan sisi negatif?

Algoritma ini membuat jarak simpul final begitu simpul itu menjadi yang terdekat dalam antrean. Sisi negatif yang ditemukan kemudian masih bisa kembali ke simpul itu lewat jalan yang lebih pendek, jadi jarak finalnya bisa salah. Algoritma Bellman–Ford bisa menangani sisi negatif, asalkan tidak ada siklus dengan total negatif.

Apa bedanya Dijkstra dan BFS?

BFS menghitung jumlah sisi dan memakai antrean biasa. Algoritma Dijkstra menjumlahkan panjang sisi dan memakai antrean prioritas yang selalu memberikan simpul terdekat. Jika setiap sisi panjangnya 1, keduanya menemukan jarak yang sama.

Seberapa cepat algoritma Dijkstra?

Dengan binary heap sebagai antrean prioritas, kerjanya bertambah sesuai (V + E) log V untuk V simpul dan E sisi. Dengan Fibonacci heap, E + V log V. Aplikasi ini menyimpan antrean sebagai daftar terurut, yang mudah ditampilkan dan cukup untuk graf kecil.

Apakah graf saya dikirim ke mana pun?

Tidak. Graf dibuat dan dicari di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor