Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• O(V² + V*E) seperti yang ditulis di sini (setiap dari V putaran memindai simpul untuk menemukan nilai minimum dan memindai edge untuk melakukan relaksasi). Dengan binary heap dan adjacency list, kompleksitasnya meningkat menjadi O((V + E) log V).

Kompleksitas Ruang:

• O(V) untuk array jarak dan array visited (ditambah edge input).

Ringkasan:

• Dijkstra menemukan jarak terpendek dari satu sumber untuk bobot nonnegatif dengan secara greedy menetapkan simpul terdekat sebagai final dan melakukan relaksasi pada edge-edge-nya.
• Algoritma ini tidak bekerja dengan edge negatif; gunakan Bellman-Ford untuk edge tersebut.