Dijkstra: shortest paths with weights
In lesson 7-2, BFS found shortest paths when every edge cost 1. Give edges weights such as minutes, dollars, or distance, and BFS breaks, because fewest edges is no longer cheapest.
The smallest example says it all. A → B directly might cost 4 while A → C → B costs 1 + 2 = 3, so the two-edge route wins.
Dijkstra's algorithm fixes BFS with one substitution: replace the queue with a min-heap, the priority queue from Data Structures, keyed by total distance from the start.
The reason a heap is needed is that BFS's plain queue processes nodes in discovery order. With weights, the next node that can be finalized is the one with the smallest total distance so far, which is exactly the question a min-heap answers in O(log n).
The loop is two steps.
- Pop the unvisited node with the smallest known distance. That distance is now final, and nothing can beat it, because any other route would have to pass through something already farther away.
- Relax its neighbors. If going through this node is shorter than a neighbor's best known distance, update it and push it.
For a picture, pour water into the start node and let it spread along the pipes, wetting nodes in order of true distance. That is precisely the order the heap pops them.
The requirement is no negative edge weights. A negative edge could make a longer route cheaper later, which breaks step 1's promise, and Bellman-Ford is the algorithm for that case.
dijkstra
The heap always surfaces the closest unfinished node.
import heapq def dijkstra(graph, start): dist = {start: 0} heap = [(0, start)] while heap: d, node = heapq.heappop(heap) if d > dist.get(node, float("inf")): continue for neighbor, weight in graph[node]: nd = d + weight if nd < dist.get(neighbor, float("inf")): dist[neighbor] = nd heapq.heappush(heap, (nd, neighbor)) return dist roads = { "A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 7)], "D": [], } print(dijkstra(roads, "A"))
Output
{'A': 0, 'B': 3, 'C': 1, 'D': 4}Watch B. It first gets a tentative distance of 4 from the direct road, then improves to 3 through C, and the final answer keeps the better one.
The heap entries are (distance, node) tuples in that order, which is what makes the heap sort by distance. Reversing the pair would sort by node name and produce nonsense.
The stale (4, "B") entry is still in the heap after the improvement, and the d > dist.get(node) check skips it. That lazy-deletion trick is standard, since heaps have no cheap way to update an existing entry.
dist.get(neighbor, float("inf")) treats an unseen node as infinitely far, so the first route to any node always wins the comparison and no separate initialization pass is needed.
D ends at 4 through A → C → B → D, at 1 + 2 + 1, which beats the direct C → D edge of weight 7 for a total of 8.
The cost is O((V + E) log V), with the log coming from each push and pop.
Because BFS explores by number of edges, and with weights the cheapest route may use more edges than the direct one.
On this lesson's graph, BFS reaches B in one hop over the weight-4 road and locks that in. It never notices that A → C → B costs 3, because that route is two hops and BFS has already finished with B.
Dijkstra explores by accumulated weight instead, which is why the heap is keyed on total distance rather than on hop count.
The two are the same algorithm when all weights are equal. With every edge at weight 1, distance and hop count agree, and the heap pops in exactly the order a queue would.
The one-word trigger is worth memorizing: unweighted means BFS, and weighted with non-negative weights means Dijkstra.
Reaching for Dijkstra on an unweighted graph is not wrong, only slower by the log factor, which is a fine trade if it is the version you remember correctly under pressure.
network_delay
The classic wrapper, asking when the last node hears the signal.
import heapq def dijkstra(graph, start): dist = {start: 0} heap = [(0, start)] while heap: d, node = heapq.heappop(heap) if d > dist.get(node, float("inf")): continue for neighbor, weight in graph[node]: nd = d + weight if nd < dist.get(neighbor, float("inf")): dist[neighbor] = nd heapq.heappush(heap, (nd, neighbor)) return dist def network_delay(graph, start): dist = dijkstra(graph, start) if len(dist) < len(graph): return -1 return max(dist.values()) net = { "A": [("B", 1), ("C", 4)], "B": [("C", 2)], "C": [], } print(network_delay(net, "A")) lonely = {"A": [("B", 1)], "B": [], "C": []} print(network_delay(lonely, "A"))
Output
3 -1
dist only contains nodes the search actually reached, so comparing len(dist) with len(graph) detects the unreachable case without any extra bookkeeping.
The moment the last node hears the signal is max(dist.values()), since the signal travels to every node in parallel and the total delay is set by the slowest arrival.
In net, C is reached at time 3 through B, at 1 + 2, beating the direct weight-4 edge. That improvement is the whole reason Dijkstra is needed here.
In lonely, node C has no incoming edge at all, so dist has two entries against three nodes and the function returns −1.
The pattern to notice is that the algorithm is untouched. Dijkstra returns distances, and the problem-specific part is two lines that interpret them, which is how most weighted-graph interview questions are shaped.
Use Dijkstra.
The edges carry weights, which rules out BFS immediately, since BFS orders by edge count as lesson 7-2 showed.
DFS is not a candidate either, because it imposes no distance order at all and would return whatever route it happened to wander down first.
Non-negative weights are exactly Dijkstra's requirement, and travel times satisfy it, since no road takes negative minutes.
If the edges were all equal you would downgrade to BFS, which is simpler and faster by the log factor.
If some weights were negative, such as a route that refunds a toll, Dijkstra's finality promise breaks and Bellman-Ford handles it at O(V·E). Naming that boundary is part of a complete answer.