Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 63 ยท Graphs for Contests

Shortest Paths in Practice

Pick the right shortest-path algorithm for a contest: Dijkstra with heapq, state-expanded graphs, Bellman-Ford with negative edges, and Floyd-Warshall limits.

When edges have different costs, BFS no longer finds the cheapest route. Contest problems then ask for a shortest path in a weighted graph: cheapest flight, fastest route with a discount, smallest cost with a rule about fuel or coupons. Four tools cover nearly all of them, and most of the skill is choosing the right one for the limits.

For the algorithms themselves, see Dijkstra, Bellman-Ford, Floyd-Warshall and Shortest Path Variants. Here we focus on how they behave in a Python contest and how to adapt them. If every edge has the same cost, or costs 0 and 1 only, go back to Graph Problems: Modeling and Traversal.

Which algorithm?

Situation Algorithm Time
Non-negative weights, one source Dijkstra with a heap O((V + E) log V)
Negative edges, one source Bellman-Ford O(V * E)
All pairs, V up to a few hundred Floyd-Warshall O(V^3)
All weights equal BFS O(V + E)
Weights 0 or 1 0-1 BFS O(V + E)
flowchart TD
    A["Weighted shortest path"] --> B{"Any negative edge?"}
    B -- "Yes" --> C["Bellman-Ford (or Floyd for all pairs)"]
    B -- "No" --> D{"All pairs and V small?"}
    D -- "Yes" --> E["Floyd-Warshall"]
    D -- "No" --> F["Dijkstra with heapq"]

A negative edge rules out Dijkstra; many sources with small V point to Floyd-Warshall.

Dijkstra with heapq

Python has no decrease-key operation in heapq, so the standard trick is lazy deletion: push a new (distance, vertex) pair whenever you find a better distance, and when you pop a pair, skip it if its distance is already worse than dist[vertex]. The heap may hold a few stale entries, but each edge adds at most one, so the total stays O(E log E).

Keep a parent array while relaxing so you can rebuild the path. Store the graph as an adjacency list: graph[u] is a list of (v, w) pairs.

Python Dijkstra with lazy deletion and path recovery

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Dijkstra is correct only because a vertex popped with its smallest distance can never be improved later, and that argument breaks down with a negative edge. Never use Dijkstra on negative weights.

Two small speed habits for Python: read the graph with fast input (see Python for Contests), and store the pair as a single integer d * N + v when the numbers are small enough, so the heap compares plain integers instead of tuples.

State-expanded shortest paths

Often the cheapest route depends on more than the current city. A typical statement: "You may use a discount coupon on at most one flight, halving its price. What is the minimum cost from city 0 to city n - 1?"

The extra information, whether the coupon is already used, becomes part of the vertex. Each vertex is (city, used) with used in {0, 1}. From (u, 0) you can pay w and go to (v, 0), or pay w // 2 and go to (v, 1). From (u, 1) you can only pay w and stay at used = 1. The answer is the smaller of dist[(n - 1, 0)] and dist[(n - 1, 1)].

The same method handles "at most k stops" (state: stops used), "fuel left" (state: fuel), or "direction of arrival" (state: direction). The state count is V * (number of extra values), so keep the extra part small.

Python Dijkstra on a state-expanded graph: one coupon

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force uses the fact that the coupon is applied to a single edge of the final route; trying each edge as the discounted one and taking the best result is the same question asked slowly.

Bellman-Ford and negative edges

Bellman-Ford relaxes every edge, and repeats this V - 1 times. A shortest path uses at most V - 1 edges, so after V - 1 rounds all distances are final. If a V-th round still improves something, the graph has a negative cycle reachable from the source, and "shortest" is not defined for vertices that can reach it.

Two implementation tips: stop early when a whole round changes nothing, and do not relax from vertices whose distance is still infinity (adding to infinity is harmless in Python floats, but it is cleaner to skip).

Python Bellman-Ford with negative-cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For problems that ask "can I make infinite profit?" the unreachable-cycle case is exactly why the dist[u] != INF check matters.

Floyd-Warshall and its limits

When you need the distance between every pair of vertices, Floyd-Warshall is three nested loops: for each intermediate vertex k, try improving dist[i][j] through k. Loop order matters: k must be the outermost loop.

The cost is V^3. In C++ that is fine for V = 400. In pure Python, 400^3 = 64 million inner steps is far too slow for a contest limit. There are two fixes: restrict yourself to V of about 100, or vectorize the two inner loops with NumPy. Each value of k becomes one array operation on a V x V matrix, so the Python loop runs only V times. If the judge does not provide NumPy, fall back to running Dijkstra from each source when the graph is sparse.

Python Floyd-Warshall in pure Python and in NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

INF is a large integer, not float("inf"), so the NumPy arrays stay integers. Choose it so that INF + INF does not overflow your type in other languages: in 64-bit C++ you would use about 10^18 / 2.

Contest checklist

  • Read the limits first: V, E, weight range, negative edges?
  • Dijkstra needs non-negative weights; if some are negative, think Bellman-Ford, or whether a transformation (such as adding a constant per edge) is valid for your question.
  • Distances can exceed 32 bits in other languages. Python integers are fine, but know the trap when translating.
  • With "at most k" or "exactly k" something, add it to the state.
  • Test on tiny random graphs against a slow reference, as in the examples above. See Stress Testing with a Brute Force.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why do we skip a popped heap entry when d > dist[u]?

    Python's heapq cannot decrease a key, so improved distances are pushed as new entries. Older, worse entries are ignored when popped.
  2. 2. A graph has an edge of weight -2 and no negative cycle. Which algorithm is safe for a single source?

    Dijkstra assumes a finalized vertex cannot be improved, which negative edges break. Bellman-Ford makes no such assumption.
  3. 3. In Floyd-Warshall, which loop must be outermost?

    After the k-th outer iteration, dist[i][j] is the best path using only the first k vertices as intermediates. Another loop order breaks that invariant.
  4. 4. Fuel is limited to F units and each edge uses some fuel. How do you model the shortest path with Dijkstra?

    The remaining fuel changes which moves are possible, so it is part of the state. The graph has V * (F + 1) vertices.

Summary

  • Choose the algorithm from the limits: BFS or 0-1 BFS for tiny weights, Dijkstra for non-negative weights, Bellman-Ford for negatives, Floyd-Warshall for all pairs on small graphs.
  • Dijkstra in Python uses heapq with lazy deletion and a d > dist[u] skip.
  • Extra conditions (coupons, fuel, stops) are added to the vertex, producing a state-expanded graph.
  • Bellman-Ford detects reachable negative cycles when a round after V - 1 still improves a distance.
  • Floyd-Warshall is O(V^3) with k outermost; vectorize with NumPy in Python or keep V small.

Next: Trees, Diameters and LCA