Dijkstra's Algorithm

The Idea

With weighted edges, fewest hops stops meaning cheapest. Dijkstra keeps a tentative distance for every node and repeatedly finalises whichever unfinished node is currently nearest, relaxing its edges as it goes. A min-heap supplies that nearest node. Negative weights break the guarantee.

Real-World Example

A content network choosing how to move a video between data centres. The direct link is congested at 9 ms, while hopping through a quiet relay costs 2 ms plus 3 ms. Fewer hops, slower delivery — the weights decide, and the router keeps relaxing until no cheaper chain is left.

The Code

import heapq
g = {"edge": [("hub", 9), ("relay", 2)], "relay": [("hub", 3), ("core", 8)],
     "hub": [("core", 1)], "core": []}
dist = {n: float("inf") for n in g}
dist["edge"] = 0
pq = [(0, "edge")]
while pq:
    d, n = heapq.heappop(pq)         # nearest unfinished node
    if d > dist[n]:
        continue                     # a stale, superseded entry
    for m, w in g[n]:
        if d + w < dist[m]:          # relax: cheaper route found
            dist[m] = d + w
            heapq.heappush(pq, (dist[m], m))
print(dist)   # {'edge': 0, 'relay': 2, 'hub': 5, 'core': 6}

dist = {"a": 0, "b": 9, "c": float("inf")}
for node, w in [("b", 4), ("c", 6)]:
  if dist["a"] + w < dist[node]:
      dist[node] = dist["a"] + w
print(dist["b"], dist["c"])