Shortest paths and their assumptions

Why it matters

Weighted-graph questions reward knowing assumptions. The natural follow-ups are why your algorithm is correct, what happens with negative weights, and what changes when the number of hops is limited. The same ideas run real systems: link-state routing protocols compute Dijkstra-style shortest-path trees, distance-vector routing is a distributed form of Bellman-Ford, and navigation and scheduling systems use variants with heuristics or precomputation. Knowing which assumption each algorithm needs is what separates a memorized template from an engineering answer.

Core ideas

Relaxation. All of these algorithms keep an upper bound d[v] on each distance and improve it with relax(u, v): if d[u] + w(u, v) < d[v], set d[v] and record parent[v] = u. They differ only in the order of relaxations and in the assumptions that make that order sufficient. Parent pointers form a shortest-path tree for reconstructing routes.

Unit weights: BFS. Queue order already equals distance order, in O(V + E).

Weights 0 or 1: 0-1 BFS. Use a deque: after relaxing along a 0-weight edge push the vertex to the front, along a 1-weight edge to the back. The deque stays sorted and holds at most two distance values, so it acts like Dijkstra with a bucket queue, in O(V + E). A vertex can be pushed twice; skip stale entries when popped. Grids where some moves are free and others cost one (such as removing an obstacle) fit this.

Non-negative weights: Dijkstra. Repeatedly take the unsettled vertex u with the smallest tentative distance, settle it and relax its edges. Invariant: a settled vertex's distance is final. Argument: any other path to u leaves the settled set at some first vertex y; d[y] is at most the length of that path's prefix, d[u] ≤ d[y] because u was the minimum, and the rest of the path cannot be negative. Standard-library heaps rarely support decrease-key, so push a new (distance, vertex) pair after every improvement and skip popped entries whose distance exceeds the recorded best (lazy deletion). The heap holds O(E) entries, giving O(E log E) = O(E log V), usually written O((V + E) log V).

import heapq

def dijkstra(adj, source):
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # stale entry: lazy deletion
        for v, w in adj[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Why negative edges break it. With edges s -> a (2), s -> b (3) and b -> a (-2), Dijkstra settles a at 2 before it looks at b, although s -> b -> a costs 1, and everything relaxed from a used the wrong value. Code that re-pushes improved vertices, like the sketch above, may repair small cases, but it loses Dijkstra's guarantee and can take exponential time. Adding a constant to every edge does not help: it penalizes paths with more edges and changes which path is shortest. Johnson's algorithm instead reweights with vertex potentials computed by Bellman-Ford, which preserves shortest paths.

Negative weights: Bellman-Ford. Without a reachable negative cycle, some shortest path to every vertex uses at most V - 1 edges, so V - 1 rounds of relaxing every edge suffice: after round i, d[v] is at most the best length over paths with at most i edges. O(VE). If a further round still improves a distance, a negative cycle is reachable and distances to vertices it reaches are undefined. For "at most k edges", run k rounds but relax from a copy of the previous round's distances; in-place updates can chain several edges in one round and silently exceed the limit.

Other cases. In a DAG, relaxing vertices in topological order takes O(V + E), even with negative weights. Floyd-Warshall computes all pairs in O(V^3) and suits small dense graphs. When a path's cost is its largest edge (minimum effort, rising water), Dijkstra still works because extending a path never lowers its cost; binary search on the answer with BFS, or union-find over sorted edges, are alternatives. When a constraint matters (stops used, keys held), search over expanded states (vertex, state).

Common misconceptions

• "Dijkstra works with negative edges as long as there is no negative cycle." The settle-once argument fails; use Bellman-Ford, or Johnson-style reweighting for all pairs.
• "Mark vertices visited when pushing them, as in BFS." A vertex's distance can still improve after its first push; it is final only when popped with its current best distance.
• "Lazy deletion makes the heap grow without bound." There is at most one entry per successful relaxation, so O(E) entries, and log E is at most 2 log V.
• "In-place Bellman-Ford respects a hop limit." Copy the previous round's distances whenever the number of edges matters.
• "Bellman-Ford always runs V - 1 full rounds." It can stop as soon as a round changes nothing; V - 1 is the worst case.

How to approach it

Start every weighted problem by stating the weight model and the path-cost function (sum, maximum, product), then pick the algorithm. Say the invariant before writing code ("a popped entry that is not stale is final") and write the stale-entry check first, since it is the line most often forgotten. Test with a graph where a path with more edges is cheaper, an unreachable vertex and zero-weight edges. Graduate-level interviews usually expect a correct Dijkstra with its complexity; mid and senior candidates should expect questions on negative weights, hop limits, path reconstruction, or recomputing routes after an edge changes.