Given a weighted graph with non-negative edges, find the shortest path from a source to every other node in O((V+E) log V) with a binary heap.
Five passes over the same idea, each from a different angle. Do them in order, or jump to whichever you need.
Dijkstra is the algorithm that taught a generation of engineers what a priority queue is for. It is a greedy traversal: at each step you relax edges out of the cheapest-so-far frontier node and update tentative distances. It fails on negative edges (use Bellman-Ford) and on negative cycles (no algorithm helps). Modern applications go far beyond GPS routing — it is the backbone of multi-agent routing, network flow, and any 'cheapest path under a metric' problem.
Where this topic shows up outside its home domain:
Multi-agent routing — picking which agent handles a query — is Dijkstra over a cost graph where nodes are agents and edges are routing costs (latency, price, reliability).
Priority queues inside Dijkstra are the same data structure that lives at the heart of priority-based message brokers and rate limiters.
