Where it runs
1. The problem
A map app has to take you from home to the airport. Some roads are short but full of traffic. Some are long but empty. You want the route that takes the least total time, however many turns it has.
So counting roads does not help here: three fast highway roads can beat two slow city streets. Each road has a weight (a cost, such as minutes, kilometres or delay). You want the smallest total cost to reach each place.
The same task shows up in a network of computers. Each link has a measured delay. You want the smallest total delay from one computer to every other one.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includeddijkstra(6, [[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], [[4, 3], [5, 6]], [[5, 1]], []], 0)Find the shortest distance from node 0 to every node. Every distance starts at ∞, node 0 gets 0 and goes into the heap.
Bars: the current distance from node 0 to each node. A full-height bar means the node is not reached yet.
One operation is one edge check or one step inside the heap. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(V·E)O(E log V)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- cheapest/shortest path with weighted edges
- non-negative edge weights
- minimum total cost to reach every node
- network delay time / route cost, not fewest roads
- weighted graph, single-source shortest paths
Looks similar, isn't
- Graph BFS / DFS
A queue counts hops, so it assumes every edge costs the same. A heap handles real weights.
- Binary heap / priority queue
The heap is the tool this runs on. That page is about the container itself.
- Greedy (exchange argument)
Settling the nearest node is a greedy choice. It only holds while no weight is negative.
- Topological sort (Kahn's algorithm)
On a graph with no cycles the order relaxes edges without a heap. That is faster and allows negatives.
V nodes and E edges give O(E log V) with a heap. Negative weights break it, so use Bellman-Ford.
On LeetCode
Problems that ask for the cheapest route when edges have different non-negative costs. Dijkstra pops the closest unfinished node from a min-heap and relaxes its edges.
Run the lesson's dijkstra from k, and the answer is the largest distance, or minus 1 if some node stays at Infinity.
Multiply instead of adding and keep the largest value, with a max-heap instead of a min-heap.
Each cell is a node, and a path costs its single biggest step, so take the max instead of the sum when relaxing.
Keep the adjacency list in the class, add edges to it, and run Dijkstra for each query.