AlgoWiki

Dijkstra's algorithm solves the single-source shortest path problem for graphs with non-negative edge weights.

It maintains a set of vertices with known shortest distances and iteratively expands this set using a greedy approach.

Steps:

1. Initialize distances and priority queue
2. Pick the vertex with the smallest tentative distance
3. Update distances to its neighbors
4. Repeat until all vertices are processed

Using a priority queue (e.g., a min-heap) makes the algorithm more efficient on sparse graphs.