Shortest paths: Dijkstra and friends

When edges have costs

In a weighted graph, each edge carries a number: kilometres, minutes, or a ticket price. The length of a path is the SUM of its edge weights, not the number of edges. A direct flight might cost ₹9,000 while a route with one stop costs ₹3,500 + ₹2,500 = ₹6,000 (made-up fares). The cheapest path can have more edges.

Why BFS fails

BFS settles a vertex the first time it reaches it, by the fewest edges. With edges 0 → 2 costing 10, and 0 → 1 → 2 costing 1 + 1, BFS reaches 2 directly in one step and reports a cost of 10, but the true cheapest cost is 2. We need an algorithm that settles vertices in order of their total distance.

Dijkstra's idea

Dijkstra's algorithm keeps a best-known distance for every vertex: 0 for the source and infinity for the rest. It repeatedly picks the unfinished vertex with the smallest known distance and relaxes its edges: for an edge u → v with weight w, if dist[u] + w is smaller than dist[v], it updates dist[v]. With non-negative weights, the closest unfinished vertex can never be improved later, because any other route to it would pass through a vertex that is at least as far away and then add more non-negative weight.

A min-heap (heapq, Module 8) finds the closest vertex fast. Python's heapq has no "decrease key" operation, so we use lazy deletion: when a distance improves, push a new (distance, vertex) pair and leave the old one in the heap. When a pair is popped whose distance is larger than the best known, it is stale, and we skip it.

import heapq

def dijkstra(adj, src):
    dist = {u: float("inf") for u in adj}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # stale entry: a shorter path was found later
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

adj = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": []}
print(dijkstra(adj, "A"))   # Output: {'A': 0, 'B': 3, 'C': 1, 'D': 4}

Cost: each edge can push one entry, so the heap holds O(E) entries, and each push or pop is O(log E) = O(log V). Total time O((V + E) log V), space O(V + E).

No negative edges

Dijkstra can give wrong answers when an edge weight is negative. With A → B costing 2, A → C costing 3 and C → B costing −2, it settles B at 2, but the true cheapest cost is 3 − 2 = 1. Negative edges appear in problems about gains and losses, such as currency exchange.

Friends of Dijkstra

• Bellman-Ford: relax EVERY edge, V − 1 times in total. It allows negative edges and runs in O(V × E). If a V-th round can still improve some distance, the graph has a negative cycle (a loop whose total is below zero) reachable from the source, and "shortest" is not defined.
• 0-1 BFS: when every weight is 0 or 1, use a deque; push to the front for a 0-edge and to the back for a 1-edge. O(V + E).
• Floyd–Warshall: shortest paths between ALL pairs with three nested loops over k, i and j, updating dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). O(V³) time and O(V²) space, so only for small graphs (a few hundred vertices). It allows negative edges but not negative cycles.
• Plain BFS: still the best choice when every edge has the same weight.

How map apps fit in

A navigation app models roads as a weighted directed graph, where the weight is the expected travel time, which changes with traffic. Dijkstra's algorithm is the textbook starting point. Real routing engines for a whole country use more advanced methods on top of it, such as A* search (which adds a smart estimate of the remaining distance) and heavy preprocessing of the road network, so that a route across thousands of kilometres is found in milliseconds. In an interview, it is good to say this.

Common mistakes

• Marking a vertex as done when it is pushed (as in BFS). Fix: a vertex is final only when it is popped with its current best distance.
• Pushing (vertex, distance) instead of (distance, vertex). heapq orders tuples by their first item. Fix: put the distance first.
• Leaving out the stale check. The answer stays right, but stale pops redo work, which can be much slower. Fix: if d > dist[u]: continue.
• Using Dijkstra with negative weights. Fix: Bellman-Ford.
• Forgetting both directions for two-way roads, or returning infinity where the prompt asks for -1. Fix: read the input format and the output rule twice.