Skip to content
Tutorials Center
My learning

Topics

Lesson 138 of 225 ยท Shortest Paths and Spanning Trees

0-1 BFS, A* and Other Shortest Paths

Faster shortest paths for special graphs: 0-1 BFS with a deque, DAG relaxation, A* with a heuristic on a grid, bidirectional search and Johnson's reweighting.

Dijkstra works on any graph with non-negative weights, and Bellman-Ford works even with negative ones. But general-purpose tools pay for their generality. When your graph has extra structure, such as only two kinds of edge cost, no cycles, a known destination, or a start and goal that you can search from both ends, there is usually a simpler or faster algorithm.

This lesson collects the most useful of these specialists: 0-1 BFS (edge costs 0 or 1), shortest paths in a DAG (one pass in topological order), A* (use a guess about the remaining distance), bidirectional search (meet in the middle), and Johnson's algorithm (all pairs on sparse graphs with negative edges). Each one is short, and each shows a different way to exploit structure.

0-1 BFS: when edges cost 0 or 1

Plain BFS finds shortest paths when every edge costs 1, using a queue. Dijkstra handles any non-negative costs using a heap, paying a log factor. If the costs are only 0 or 1, you can have the best of both with a deque (double-ended queue):

  • Relax an edge of cost 0: the neighbor is just as close as the current vertex, so push it on the front.
  • Relax an edge of cost 1: push it on the back.

The deque always stays sorted by distance, with at most two distinct distance values in it (d and d + 1), so it plays the role of Dijkstra's heap in O(1) per operation. Total time is O(V + E).

TEXT
deque (front ... back):   [ d, d, d | d+1, d+1 ]
cost 0 edge  -> appendleft   (joins the d group)
cost 1 edge  -> append       (joins the d+1 group)

A typical problem: a grid where 1 is a wall. Moving into a free cell costs 0, moving into a wall costs 1 (you smash it). What is the fewest walls you must smash to go from the top-left to the bottom-right corner?

Python 0-1 BFS: fewest walls to break in a grid

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 answer is 2: every route has to cross column 5, which is solid wall, and every route to that column must first break through either column 3 or the wall cell at the bottom of column 4. A cell can be pushed more than once if a cheaper route to it appears later, which is why the check dist + w < dist[next] guards every push. Compared with Dijkstra, the answer is identical but each queue operation is O(1) rather than O(log V).

Python 0-1 BFS agrees with Dijkstra

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.

Other typical 0-1 problems: the fewest edges you must reverse so a path exists in a directed graph (following an edge costs 0, going against it costs 1), or the fewest direction changes in a maze. The trick generalizes to small integer weights (Dial's algorithm uses an array of buckets).

Shortest paths in a DAG

If the graph is a directed acyclic graph, no cycle can ever make a distance smaller later. Process the vertices in topological order and relax each vertex's outgoing edges once. When we reach a vertex, every edge into it has already been relaxed, so its distance is final. That is O(V + E), faster than Dijkstra, and negative weights are fine because there are no cycles.

Python DAG shortest and longest paths

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 longest path is just the shortest path with negated weights. In a general graph the longest simple path is NP-hard, but in a DAG it is easy. This is exactly the "critical path" computation used in project scheduling.

A*: shortest path with a sense of direction

Dijkstra explores outward in all directions like a ripple, even directions that obviously lead away from the goal. If you know where the goal is, you can do better. A* (say "A star") keeps Dijkstra's structure but orders the heap by

TEXT
f(v) = g(v) + h(v)
g(v) = cost of the best known path from the start to v
h(v) = a guess (heuristic) of the cost from v to the goal

On a grid with 4-direction moves of cost 1, a natural heuristic is the Manhattan distance |row difference| + |column difference|. It never overestimates, because you cannot reach the goal in fewer steps than that. A heuristic that never overestimates is called admissible, and with an admissible heuristic A* returns an optimal path while usually expanding far fewer vertices than Dijkstra. If h is also consistent (h(u) <= cost(u, v) + h(v) for every edge), each vertex is expanded at most once, as in Dijkstra. Manhattan distance is consistent on a 4-direction grid.

With h = 0 A* is exactly Dijkstra. With a perfect h it walks straight to the goal. The better the guess, the fewer vertices it expands.

Python A* versus Dijkstra on a grid

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.

Both searches find a path of the same length, which is the optimality guarantee. The A* run expands fewer vertices because it prefers cells that look closer to G.

Watch out: if your heuristic can overestimate the true remaining cost, A* may return a path that is not shortest. For example, multiplying Manhattan distance by 2 makes the search greedy and fast, but not optimal. Use a weighted heuristic on purpose only when you accept near-optimal answers.

A* is the standard algorithm behind game pathfinding and map routing, with different heuristics: straight-line distance for roads, Manhattan or octile distance for grids, pattern databases for puzzles like the 15-puzzle.

If a path of length d must be found in a graph where each vertex has b neighbors, BFS from the start visits roughly b^d vertices. Two BFS searches, one from the start and one from the goal, each only need to go depth d/2, visiting about 2ยทb^(d/2). On a grid the gain is smaller (the number of cells within distance r grows like rยฒ, not exponentially), but it is still clear.

Expand the smaller frontier one full level at a time, and stop when the two searches touch.

Python Bidirectional BFS versus plain BFS

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 distance matches, but only about half as many cells are touched, and in graphs with a high branching factor the saving is dramatic. Bidirectional search needs a way to walk backwards from the goal (trivial in undirected graphs, but on directed graphs you need the reverse adjacency list).

Johnson's algorithm: all pairs on sparse graphs

Floyd-Warshall is O(Vยณ). On a sparse graph, running Dijkstra from every vertex costs O(V ยท (V + E) log V), which is much better, but Dijkstra cannot handle negative edges. Johnson's algorithm removes the negative edges by reweighting, without changing which paths are shortest:

  1. Add a new vertex s with a 0-weight edge to every vertex. Run Bellman-Ford from s; the distances are h[v] (this also detects negative cycles).
  2. Replace every weight with w'(u, v) = w(u, v) + h[u] - h[v]. Because h is a shortest-distance table, h[v] <= h[u] + w, so every new weight is non-negative.
  3. A path from a to b changes in total length by h[a] - h[b] only (the middle terms cancel like a telescoping sum), so shortest paths stay shortest.
  4. Run Dijkstra from each vertex on the new weights, then correct: dist(a, b) = dist'(a, b) - h[a] + h[b].

The cost is one Bellman-Ford plus V Dijkstra runs: O(VยทE + VยทE log V), better than Vยณ when E is much smaller than Vยฒ.

Python Johnson's algorithm checked against Floyd-Warshall

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.

Multistage graphs: a DAG with layers

A multistage graph is a DAG whose vertices are split into stages 0, 1, ..., k, with edges only from one stage to the next. There is a single source in stage 0 and a single sink in the last stage. Think of a trip planned in legs, such as cities per day, or a production line with several machines per step. The cheapest route is a dynamic programming problem: let cost[v] be the cheapest way from v to the sink, computed stage by stage from the end:

TEXT
cost[sink] = 0
cost[v]    = min over edges (v -> w) of  w_vw + cost[w]

Because every edge leaves a stage forward, processing the stages in reverse order is already a topological order, and the algorithm is O(V + E): exactly the DAG relaxation above, with the order given for free.

Python Multistage graph by backward DP, checked against Dijkstra

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 backward DP prints the cheapest total and the route through the stages. It also gives the best route from every vertex to the sink for free, because cost[v] is stored for all of them. Run the same code forward (from the source) when you need distances to many sinks instead.

Dial's algorithm: Dijkstra with buckets

If all edge weights are small non-negative integers (at most C), Dijkstra's heap is overkill. Distances are integers too, so keep an array of buckets: bucket[d] holds the vertices whose current tentative distance is d. Scan d = 0, 1, 2, ... and settle the vertices in each bucket. No heap operations are needed, only appending to lists.

The largest possible distance is C * (V - 1), so there are at most that many buckets, giving O(V + E + C V) time. For tiny C (such as weights 1 to 5) this is effectively linear. A circular array of C + 1 buckets brings the memory down, since at any moment all tentative distances lie within C of the current one. Dial's algorithm is the generalisation of the 0-1 BFS from the start of this lesson: with C = 1 it is the same idea.

Python Dial's bucket queue

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.

Note the stale entry check: a vertex may be appended to several buckets as its tentative distance drops, and only the entry in the bucket matching the final dist counts. Zero-weight edges work too, because a vertex appended to the current bucket is processed in the same scan.

D'Esopo-Pape: a deque heuristic

The D'Esopo-Pape algorithm keeps one queue (a deque) and one rule about where a vertex goes when its distance improves:

  • A vertex that has never been in the queue is pushed at the back.
  • A vertex that left the queue earlier and just got a better distance goes to the front: it has already spread its old distance, so refreshing it first corrects the damage quickly.
  • A vertex already in the queue just updates its distance and stays.

It needs non-negative weights, and it often beats Dijkstra on sparse road-like graphs. There is a catch: the worst case is exponential, and carefully built graphs hit it, so it is a practical heuristic, not a guaranteed algorithm.

Python D'Esopo-Pape against Dijkstra

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.

On random graphs the answers match Dijkstra exactly, and no graph needed more than about two visits per vertex on average, which is why the method feels fast. Do not rely on that when an adversary chooses the input.

Which one should I use?

Situation Algorithm Time
All edges cost 1 BFS O(V + E)
Edge costs 0 or 1 0-1 BFS O(V + E)
Graph is a DAG (negatives ok) Topological relaxation O(V + E)
Layered DAG (stages) Backward DP O(V + E)
Small integer weights (at most C) Dial buckets O(V + E + C V)
Non-negative weights Dijkstra O((V + E) log V)
Non-negative, sparse, road-like D'Esopo-Pape (heuristic) fast in practice, exponential worst case
Known goal, good heuristic A* usually far fewer expansions
Single pair, huge unweighted graph Bidirectional BFS about b^(d/2) instead of b^d
Negative edges, one source Bellman-Ford O(VยทE)
All pairs, dense Floyd-Warshall O(Vยณ)
All pairs, sparse, negatives Johnson O(VยทE log V)

Common mistakes

  • 0-1 BFS with a plain queue. Zero-cost edges must go to the front, otherwise distances come out wrong.
  • Marking visited when pushing in 0-1 BFS or A*. A vertex can be reached again more cheaply, so compare distances instead of using a visited flag at push time.
  • An inadmissible heuristic in A*. It silently loses optimality.
  • Stopping bidirectional search in the middle of a level. Finish the level and take the minimum over all meeting points, otherwise the distance can be off by one.
  • Forgetting that the DAG method needs a valid topological order. On a graph with a cycle there is none.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In 0-1 BFS, where do you push a vertex reached through an edge of cost 0?

    A zero-cost neighbor is exactly as far as the current vertex, so it belongs with the current distance group at the front.
  2. 2. Why can shortest paths in a DAG be found in O(V + E) even with negative edges?

    Every edge into a vertex comes from an earlier vertex in the order, so one relaxation per edge is enough.
  3. 3. Which heuristic property guarantees that A* returns an optimal path?

    An admissible heuristic never claims the goal is farther than it really is, so A* cannot discard the optimal route.
  4. 4. What does A* become when h(v) = 0 for every vertex?

    The priority f = g + 0 is the distance from the start, which is precisely Dijkstra's ordering.
  5. 5. What is the purpose of the potentials h in Johnson's algorithm?

    w'(u, v) = w + h[u] - h[v] is non-negative, and any path's total changes by a constant that depends only on its endpoints.

Summary

  • 0-1 BFS: deque, front for cost 0, back for cost 1; O(V + E).
  • DAG shortest paths: relax edges in topological order; O(V + E); allows negative weights; longest path by negating.
  • A*: order the heap by g + h; an admissible (and consistent) heuristic keeps the result optimal while expanding fewer vertices.
  • Bidirectional BFS searches from both ends and meets in the middle, touching far fewer vertices.
  • Johnson: Bellman-Ford potentials make weights non-negative, then run Dijkstra from every vertex.
  • Pick the algorithm that matches the structure of your graph.

Next: Minimum Spanning Trees: Kruskal and Prim