Algoritma Dijkstra


Diberi graf berwajaran terarah atau tidak terarah dengan n bucu dan m tepi. Berat semua tepi adalah bukan negatif. Beberapa titik permulaan s ditentukan. Anda perlu mencari panjang laluan terpendek dari bucu s ke semua bucu lain dan juga menyediakan cara untuk mencetak sendiri laluan terpendek.
 
Masalah ini dipanggil "masalah laluan terpendek sumber tunggal" (masalah laluan terpendek sumber tunggal).

Melaksanakan tugas yang sama seperti 1-K BFS, tetapi tanpa mengambil kira K. Juga, seperti 1-K BFS, ia tidak mengendalikan tepi negatif dengan betul

Algoritma:
Algoritma Dijkstra sendiri terdiri daripada N lelaran. Pada lelaran seterusnya, puncak V  dengan jarak terkecil dari antara bucu yang belum ditandakan, bucu ini menjadi bertanda dan kelonggaran bucu jiran berlaku daripadanya.


 tingkah laku asimptotik akhir algoritma ialah: O(n2+ m)

Training problem

Dijkstra: Permulaan (C++)

Training problem

Dijkstra

Oleh kerana tingkah laku asimptotik pelaksanaan naif algoritma Dijkstra ialah: \(O(n^2 + m)\), maka apabila bilangan bucu bertambah, kepantasan kerja menjadi tidak memuaskan.
 Pelbagai struktur data boleh digunakan untuk penambahbaikan: Timbunan Fibonacci, set set atau baris gilir keutamaan priority_queue. 
Pertimbangkan contoh dengan set, akibatnya, asimptotik terakhir ialah: \(O(n log (m))\) , butiran.

Training problem

Algoritma Dijkstra dalam set O(M logN) c: Mula (C++)