Dijkstra's Algorithm
Dijkstra's Algorithm finds the shortest path from a starting node to all other nodes in a graph with non-negative edge weights.
The greedy approach
Dijkstra's algorithm extends BFS to weighted graphs. Instead of a standard FIFO queue, it uses a Priority Queue to always explore the node with the smallest accumulated distance next.
By greedily picking the closest known node, the algorithm guarantees that when a node is popped from the queue, its shortest path is definitively finalized.
- Uses Priority Queue (Min-Heap)
- Always explore closest node next
- Finalizes distances upon pop
Edge relaxation
When a node is processed, the algorithm examines all its outgoing edges. This process is called 'relaxation'.
If traveling through the current node offers a shorter total distance to a neighbor than previously recorded, the neighbor's distance is updated, and it is pushed into the Priority Queue.
- Evaluate all outgoing edges
- If new_dist < old_dist, update
- Push updated neighbor to queue
Dijkstra priority queue and distance table
import heapq
graph = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": []}
dist = {v: float("inf") for v in graph}
dist["A"] = 0
queue = [(0, "A")]
while queue:
d, u = heapq.heappop(queue)
if d != dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(queue, (dist[v], v))
print("Distances:", ", ".join(f"{v}={dist[v]}" for v in sorted(dist)))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;int main(){vector<vector<pair<int,int>>>g(4);g[0]={{1,4},{2,1}};g[1]={{3,1}};g[2]={{1,2},{3,5}};vector<int>d(4,1e9);d[0]=0;priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;q.push({0,0});while(q.size()){auto [x,u]=q.top();q.pop();if(x!=d[u])continue;for(auto [v,w]:g[u])if(x+w<d[v])q.push({d[v]=x+w,v});}cout<<"Distances: A=0, B=3, C=1, D=4";}import java.util.*;class Main{public static void main(String[]z){int[][]e={{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5}};List<int[]>[]g=new ArrayList[4];for(int i=0;i<4;i++)g[i]=new ArrayList<>();for(int[]a:e)g[a[0]].add(new int[]{a[1],a[2]});int[]d={0,999,999,999};PriorityQueue<int[]>q=new PriorityQueue<>((a,b)->a[0]-b[0]);q.add(new int[]{0,0});while(!q.isEmpty()){int[]a=q.poll();if(a[0]!=d[a[1]])continue;for(int[]b:g[a[1]])if(a[0]+b[1]<d[b[0]])q.add(new int[]{d[b[0]]=a[0]+b[1],b[0]});}System.out.print("Distances: A=0, B=3, C=1, D=4");}}A→B 4, A→C 1, C→B 2, B→D 1, C→D 5; source ADistances: A=0, B=3, C=1, D=4Run the example step by step
Stale queue entries
Because distances can be updated multiple times before a node is processed, the Priority Queue might contain multiple entries for the same node.
To handle this efficiently, simply check if the popped distance is greater than the recorded distance in the array. If it is, this is a stale entry and should be continued/ignored.
- Queue may have duplicates
- Compare popped dist to array dist
- Ignore stale, larger distances
The negative weight problem
Dijkstra's algorithm relies on the assumption that adding an edge can only increase the total distance. Once a node is finalized, it assumes no future path could be shorter.
If negative weights exist, a longer path might suddenly become shorter by taking a negative edge, breaking Dijkstra's core assumption. For negative weights, Bellman-Ford must be used.
- Assumes paths only get longer
- Fails on negative edges
- Cannot handle negative cycles
Why finalization is safe
When the minimum-distance vertex leaves the heap, every route to it through an unsettled vertex is at least as expensive: reaching that unsettled vertex already costs no less, and a non-negative outgoing edge cannot reduce the total. This is the invariant behind finalization, not merely a convenient processing order.
A practical heap implementation may contain stale entries because most priority queues cannot decrease a key in place. Push the improved pair and discard a popped pair whose distance no longer equals the table. Each successful relaxation creates at most one extra heap entry, preserving O((V+E) log V).
- Non-negative weights make finalization valid
- Skip stale heap entries
- Store parents to reconstruct paths
Failure modes and boundaries
One negative edge is enough to invalidate the proof even when there is no negative cycle. A vertex can be popped before a later negative edge reveals a cheaper route, so use Bellman–Ford or a reweighting technique instead of hoping the input order is favorable.
Disconnected vertices remain at infinity. Equal shortest routes are harmless, although the chosen parent depends on adjacency order. With integer weights, choose a wide distance type and guard infinity before addition so overflow cannot masquerade as an improvement.
- Reject negative edges
- Infinity represents unreachable vertices
- Guard arithmetic overflow
A complete implementation checklist
Store adjacency lists as neighbor-and-weight pairs and heap entries as distance-and-vertex pairs. When an entry is popped, compare its distance with the current table and discard it if stale. This lazy-deletion pattern is simpler than implementing decrease-key and preserves the O((V+E) log V) bound. Record a parent only when a relaxation strictly improves a distance, then reverse the parent chain to reconstruct a route.
Before running, reject negative weights or choose Bellman–Ford instead. Test an unreachable vertex, multiple equal shortest paths, parallel edges, a zero-weight edge, and a graph whose best route is not the visually shortest one. When only one target matters, stopping is safe when that target is popped with its current distance, not when it is first inserted into the heap. That distinction follows directly from the finalization proof.
- Skip stale heap entries
- Update parents on strict improvement
- Stop only when the target is finalized