Where Dijkstra Runs the World

Dijkstra is not a textbook curiosity - it runs quietly under software you use every day. This phase covers where it shows up, the small tweak that makes it even faster for point-to-point routing, and the one kind of input that silently breaks it.

Where it actually runs

• Maps and navigation. Road networks are weighted graphs - intersections are nodes, roads are edges, and the weight is travel time (adjusted live for traffic). Finding your route is a shortest-path query. Real map engines precompute and layer tricks on top, but the shortest-path core is Dijkstra's idea.
• Network routing. Link-state protocols like OSPF have each router build a map of the network and run Dijkstra to decide the cheapest next hop for every destination. The packets carrying this page were routed by descendants of this algorithm.
• Anything with a weighted "cheapest route" question. Flight-fare connections, transit trip planners, latency-aware request routing, even pathfinding costs in some games - all shortest-path problems wearing different clothes.

A* : Dijkstra plus a hunch

Plain Dijkstra explores outward in every direction equally, because it has no idea where the target is. If you are routing to one specific destination, that wastes effort exploring away from the goal. A* ("A star") fixes this with a heuristic: an estimate of the remaining distance from each node to the target (for maps, the straight-line distance). It prioritizes nodes by distance_so_far + estimated_distance_left, so it explores toward the goal first and reaches it sooner. When the heuristic is always 0 - no guess at all - A* is exactly Dijkstra. As long as the heuristic never overestimates the true remaining distance, A* still returns the genuine shortest path, just faster.

💡 Key point. Dijkstra answers "shortest paths to everywhere" from one source. A* answers "shortest path to this one target" and uses knowing the target to skip irrelevant exploration. Same skeleton, one extra term in the priority.

The gotcha: negative edge weights break it

Dijkstra's correctness rests entirely on the phase-1 promise: when you finalize the closest unvisited node, no cheaper route to it can exist. A negative edge weight destroys that promise - a later edge can lower a total, so a node you already finalized might have had a cheaper path you never reconsidered.

import heapq

# C -> B has a NEGATIVE weight
graph = {
    "A": [("B", 1), ("C", 2)],
    "B": [],
    "C": [("B", -2)],
}

def dijkstra_finalizing(graph, start):
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    visited = set()
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)                 # node is now final - never revisited
        for neighbor, weight in graph[node]:
            if neighbor not in visited and d + weight < dist[neighbor]:
                dist[neighbor] = d + weight
                heapq.heappush(pq, (d + weight, neighbor))
    return dist

print("Dijkstra says:", dijkstra_finalizing(graph, "A"))
print("But A -> C -> B really costs:", 2 + (-2))

Dijkstra says: {'A': 0, 'B': 1, 'C': 2}
But A -> C -> B really costs: 0

What just happened: Dijkstra finalized B at distance 1 (the direct A -> B edge) and marked it done. Only afterward did it expand C, whose -2 edge to B would have made A -> C -> B cost 2 - 2 = 0 - cheaper. But B was already finalized, so that better route was never applied. The reported distance of 1 is simply wrong; the true answer is 0.

⚠️ Gotcha. This failure is silent - no crash, no warning, just a wrong number. Dropping the "finalize once" rule to keep re-opening nodes does not save you either: with negative weights that can do exponential work, and a negative cycle (a loop whose weights sum below zero) has no shortest path at all, since you could circle it forever driving the cost down. Do not reach for a "patched" Dijkstra on negative weights.

📝 Terminology. For graphs that genuinely have negative edge weights (but no negative cycle), use Bellman-Ford. It relaxes every edge V - 1 times instead of trusting a greedy finalize order, so it tolerates negatives and can even detect a negative cycle. It is slower - O(V * E) versus Dijkstra's O((V + E) log V) - which is the price of not assuming edges only add cost.

What we built

• BFS finds shortest paths only when every edge costs the same; weights need Dijkstra.
• Dijkstra greedily finalizes the closest unvisited node and relaxes its edges, using a min-heap to find that node fast.
• The stale-entry skip lets a plain heap stand in for a decrease-key heap.
• A* adds a goal-direction heuristic to reach a single target faster; with a zero heuristic it is Dijkstra.
• Negative edges break Dijkstra's core assumption - use Bellman-Ford there.

Check yourself

[
  {
    "q": "What is A* in one line?",
    "choices": ["A faster sorting algorithm", "Dijkstra plus a heuristic estimate of the remaining distance to the goal, so it explores toward the target first", "BFS applied to weighted graphs", "Dijkstra run backward from the target"],
    "answer": 1,
    "explain": "A* prioritizes nodes by distance-so-far plus an estimate of distance-left, steering the search toward one target. With a zero heuristic it reduces exactly to Dijkstra."
  },
  {
    "q": "Why does a negative edge weight break Dijkstra?",
    "choices": ["A min-heap cannot hold negative numbers", "Once Dijkstra finalizes a node it never reconsiders it, but a later negative edge could have created a shorter path to that node", "Negative weights make the graph infinite", "It does not actually break it"],
    "answer": 1,
    "explain": "Finalizing assumes no cheaper route to a settled node can appear later. A negative edge can lower a total after the fact, so the already-finalized distance can be wrong."
  },
  {
    "q": "Which algorithm correctly handles a graph with negative edge weights but no negative cycle?",
    "choices": ["Binary search", "Bellman-Ford", "Bubble sort", "Breadth-first search"],
    "answer": 1,
    "explain": "Bellman-Ford relaxes every edge V-1 times rather than trusting a greedy finalize order, so it tolerates negative weights and can even flag a negative cycle. The cost is its slower O(V*E) running time."
  }
]