Explain Dijkstra's Algorithm. When does it fail?

Difficulty: 5/10

shortest path, negative edge weights, priority queue

Dijkstra's Shortest Path

Dijkstra's algorithm computes single-source shortest paths in graphs with non-negative edge weights. It repeatedly selects the unsettled vertex with the smallest tentative distance, relaxes its outgoing edges, and finalizes that distance. A priority queue is commonly used to efficiently select the next vertex.

javascript

1
Requires non-negative edge weights.
2
Negative edges can invalidate the greedy finalization step.
3
Binary heap implementation: typically O((V+E) log V).
4
For sparse graphs, adjacency lists are preferred.
5
Bellman-Ford is appropriate when negative edges must be supported.

Scenario Questions

0-2 years experience

Follow-up Questions