Shortest paths with weights
Dijkstra's algorithm finds the shortest distance from a source vertex to every other vertex when all edge weights are non negative. Unlike BFS, which counts edges, Dijkstra sums real weights.
The greedy frontier
The algorithm keeps a tentative distance for every vertex, starting at zero for the source and infinity elsewhere. A min heap, or priority queue, always hands back the unsettled vertex with the smallest tentative distance.
- Pop the closest unsettled vertex and mark it settled; its distance is now final.
- Relax each outgoing edge: if going through this vertex offers a shorter route to a neighbour, update that neighbour's tentative distance and push it onto the heap.
- Repeat until the heap empties.
Why non negative weights are required
Settling a vertex assumes no later, cheaper path can appear. With a negative edge, a path discovered later could undercut a settled distance, breaking the greedy guarantee. For negative edges you need Bellman Ford instead.
Using a binary heap, the running cost grows close to the number of edges times the logarithm of the vertex count, which is efficient for sparse graphs.
Key idea
Dijkstra repeatedly settles the closest unsettled vertex from a min heap and relaxes its edges, giving shortest paths whenever every edge weight is non negative.