Graph Theory37 sections · 1633 units
Open in Course

When Dijkstra Wins

(Non-negative weights)

Dijkstra handles any non-negative weights: 00, 11, 55, 10001000. It is faster than Bellman-Ford when weights are positive.

The moment you see a negative edge, Dijkstra breaks. It assumes visiting a node again will not improve the distance.

If all weights 0\geq 0 and you need single-source distances, pick Dijkstra. With a binary heap, it runs in O((N+M)logN)O((N + M) \log N) time. For dense graphs where MN2M \approx N^2, that is O(N2logN)O(N^2 \log N). Still faster than Bellman-Ford's O(NM)O(NM).