Algorithms · Lecture Notes

Chapter 6: Shortest Paths

Finding the shortest route between two points on a map, getting a packet across a network by the cheapest path, and moving a game character around obstacles to a goal are different faces of the same problem. All of them look for a shortest path in a weighted graph. These notes begin by defining the problem and relaxation, the operation common to all the algorithms. They then treat four algorithms in the same order. Dijkstra's algorithm proceeds by finalizing the nearest vertex, and works when no weight is negative. The Bellman-Ford algorithm relaxes all edges again and again; it handles negative edges and detects negative cycles. The Floyd-Warshall algorithm computes the distances between all pairs of vertices with three nested loops. A* search estimates the distance to the goal and so steers the search toward it. Each algorithm is run step by step on example graphs, and its Java code is followed line by line. The notes close with breadth-first search for unweighted graphs and a comparison of the algorithms.

Learning outcomes

Concepts
Tell single-source, all-pairs, and single-pair shortest path problems apart; explain relaxation, the distance estimate (d), and the predecessor array (π).
Dijkstra and Bellman-Ford
Run both algorithms step by step on example graphs, fill in the distance and predecessor tables, follow their Java code, and state their complexity with reasons.
Negative edges and cycles
Show with an example why Dijkstra's algorithm fails on a negative edge; detect negative cycles with Bellman-Ford and Floyd-Warshall.
Floyd-Warshall and A*
Update the matrices D and Π for all pairs in intermediate-vertex order. Apply A* search with f = g + h, explain what it means for a heuristic to be admissible and consistent, and choose an algorithm according to the type of problem.

6.1The shortest path problem

Graph traversal algorithms tell us which vertices can be reached from a vertex. In real applications that is often not enough: the cheapest way to get there is wanted as well. Once numbers such as length, time, or cost are attached to the edges, the question is no longer "can it be reached?" but "what is the least it costs to reach?" This section defines the problem, separates its kinds, and describes relaxation, the common operation on which all the algorithms are built.

6.1.1A road network is a graph

The road map of a city is a natural graph. Intersections are vertices and the roads joining them are edges. Each road has a length or a travel time; this number is the weight of the edge. A graph whose edges carry weights is a weighted graph. If there are one-way streets, the direction of the edges matters too; the graph is then directed.

A path in a graph is a sequence of vertices joined by consecutive edges. The length of a path is the sum of the edge weights on it. In this definition what counts is not the number of edges but the sum of the weights. A path of two edges can be longer than a path of five edges.

Definition 6.1

Let G = (V, E) be a weighted graph and w(u, v) the weight of the edge (u, v). The length of a path p = ⟨v0, v1, …, vk⟩ is the sum w(p) = w(v0, v1) + w(v1, v2) + … + w(vk−1, vk).

A shortest path from s to v is a path of least length among the paths between these two vertices. This least length is the distance from s to v, written δ(s, v). If there is no path at all from s to v, we take δ(s, v) = ∞.

Figure 6.1 shows a small road network. There are several paths from Home to School. The path Home–1–2–4–School has four edges and length 4 + 2 + 3 + 3 = 12. The path Home–1–4–School has only three edges, but because the edge 1–4 costs 6 units its length is 4 + 6 + 3 = 13. The path Home–3–4–School also has three edges and also comes to 13. The shortest path is not the one with the fewest edges but the four-edge path Home–1–2–4–School: δ(Home, School) = 12.

432632723Home12Mkt3Lake4School
Figure 6.1: A small road network. Vertices are intersections, edges are roads, and the numbers are road lengths. The green edges show the shortest path (12) from Home to School. The path Home–1–4–School, with fewer edges, comes to 13.

The example shows the heart of the problem. In an unweighted graph the shortest path is the path with the fewest edges, and breadth-first search finds it directly. In a weighted graph, counting edges is not enough; the sums of the weights must be compared. This is why separate algorithms are needed for weighted graphs.

The shortest path problem turns up in many places in everyday technology. Navigation apps compute the shortest or fastest route in a road network. Internet routers decide to which neighbor to forward a packet by a shortest-path computation. The OSPF (Open Shortest Path First) protocol uses Dijkstra's algorithm, and the RIP (Routing Information Protocol) protocol uses a distributed form of Bellman-Ford. In games, characters walking around obstacles are handled by A* search. In logistics, vehicle delivery routes also rest on shortest-path computations.

Common mistake

Taking the shortest path in a weighted graph to be the path with the fewest edges. The path Home–1–4–School in Figure 6.1 has three edges but length 13; the four-edge path Home–1–2–4–School comes to 12. The number of edges decides only when all weights are equal.

6.1.2Kinds of problems

The request "find the shortest path" can come in three different forms. Which form is wanted also determines the algorithm to use.

  • Single-source shortest paths: the distances from a source s to all vertices of the graph are wanted. The result is an array holding one number per vertex. Dijkstra, Bellman-Ford, and breadth-first search on an unweighted graph solve this problem.
  • All-pairs shortest paths: the distance is wanted for every pair of vertices (u, v). The result is a matrix of size n × n. The Floyd-Warshall algorithm is designed for this problem.
  • Single-pair shortest path: only the shortest path from one start s to one goal t is wanted. A single-source algorithm can do this job too, but it expands more vertices than necessary. A* search knows the goal and steers the search toward it.

Besides the kind of problem, properties of the graph also affect the choice. The most important property is whether there are edges with negative weight. When weights are thought of as costs, a negative value may seem strange. But with edges that carry a gain or a refund, negative weights are natural: a transfer that gives a discount in a transport network, a transaction that earns a profit in a financial graph. Table 6.1 lists the algorithms of this chapter with what they find and their restrictions.

Table 6.1: Problems solved by the shortest-path algorithms, and their restrictions.
AlgorithmWhat it findsRestriction / note
Dijkstrafrom the source to all verticesedge weights must not be negative
Bellman-Fordfrom the source to all verticesworks with negative edges, detects negative cycles; slower than Dijkstra
Floyd-Warshallall pairsworks with negative edges; detects a negative cycle from the diagonal
A*from start to goalspeeds up the search with a heuristic estimate
BFSfrom the source to all verticesonly unweighted (or equal-weight) graphs

6.1.3The basic operation: relaxation

All the algorithms in this chapter work on the same idea. For each vertex, the length of the best path found so far is kept as an estimate. As the algorithm proceeds, shorter paths are found and the estimates shrink. In the end every estimate equals the true distance. Two pieces of information are stored for each vertex:

  • d[v]: the length of the shortest path from the source to v found so far. At the start it is 0 at the source and ∞ at all other vertices. ∞ means "no path found yet".
  • π[v]: the vertex that comes immediately before v on this path, called the predecessor. At the start it is undefined and is written "/" or "–".

The only operation that shrinks the estimates is relaxation. When an edge (u, v) is relaxed, the question asked is: if we take the known path from the source to u and append the edge (u, v), do we get a path to v shorter than the one we know? If so, the estimate and the predecessor of v are updated.

Definition 6.2

Relaxing the edge (u, v): if d[u] + w(u, v) < d[v], set d[v] ← d[u] + w(u, v) and π[v] ← u; otherwise nothing changes.

RELAX(u, v, w):
  if d[u] + w(u, v) < d[v]:
    d[v] = d[u] + w(u, v)
    π[v] = u

The pseudocode is the definition itself. The second line asks whether the path through u is shorter. If it is, the third line writes the new length and the fourth records that the path now comes from u. The operation consists of one comparison and at most two assignments; it takes O(1) time.

3suv059 → 8…
Figure 6.2: One relaxation step. The known path from the source to u is 5 and the edge (u, v) is 3 units. The estimate of v was 9; since 5 + 3 = 8 < 9, the estimate drops to 8 and π[v] = u.
Example 6.1

In the situation of Figure 6.2 the edge (u, v) is relaxed twice in a row. Find the result of each relaxation.

  1. First relaxation. d[u] = 5, w(u, v) = 3, d[v] = 9. The candidate length is 5 + 3 = 8. Since 8 < 9, d[v] = 8 and π[v] = u.
  2. Second relaxation. The candidate length is again 8, but now d[v] = 8. Since 8 < 8 is false, nothing changes.
  3. Result. Relaxing the same edge again does no harm; only a comparison is wasted. Unless d[u] shrinks, the second relaxation gains nothing.

Relaxation has two important properties. First, d[v] can only decrease; no relaxation ever increases an estimate. Second, d[v] never falls below the true distance δ(s, v). The reason is simple: every value written to d[v] is the length of a path from the source to v that really exists. Since no path can be shorter than a shortest path, the estimate cannot drop below the distance either. The estimate comes down from above and stops when it reaches the right value.

The difference between the algorithms lies not in relaxation but in the order in which and the number of times the edges are relaxed. Dijkstra relaxes each edge once, in a cleverly chosen order. Bellman-Ford relaxes all edges again and again without regard to order. Floyd-Warshall does the same operation on pairs of vertices, adding intermediate vertices. A* replaces Dijkstra's order with an estimate of the distance to the goal.

Common mistake

Updating only d[v] in relaxation and forgetting π[v]. The distances come out right, but the path itself cannot be rebuilt. If not just the length of the shortest path but also which vertices it passes through is wanted, the two assignments must be made together.

6.1.4Properties of shortest paths

To understand why the algorithms work, we need four properties of shortest paths. These properties are used both in designing the algorithms and in proving them correct.

Optimal substructure. Every part of a shortest path is itself a shortest path. If the path s ⇝ u ⇝ v is a shortest path from s to v, then its part s ⇝ u is a shortest path from s to u. The proof is a short contradiction. If there were a shorter path from s to u, the old part could be removed and this path put in its place. That would give a shorter path to v as well, contradicting the choice of a shortest path. Optimal substructure is the common basis of dynamic programming and greedy algorithms. Bellman-Ford and Floyd-Warshall use this property through dynamic programming, and Dijkstra through a greedy choice.

Triangle inequality. For every edge (u, v), δ(s, v) ≤ δ(s, u) + w(u, v) holds. The right side of the inequality is the length of one particular path: go to u by a shortest path and use the edge (u, v). A shortest path cannot be longer than this path. Relaxation finds the edges where this inequality is violated by the estimates and repairs them: every edge with d[v] > d[u] + w(u, v) is an opportunity for repair.

Negative cycle. A cycle whose total weight is negative is a negative cycle. If such a cycle is reachable from the source, the path gets a little shorter each time the cycle is traversed. Since the path can be shortened as much as we like, the shortest path is undefined; the distance is written −∞. This affects not only the vertices on the cycle but all vertices reached through the cycle.

Simple path. If there is no negative cycle, a shortest path contains no cycle. Removing a cycle of positive weight from a path shortens it, and removing a cycle of weight zero leaves the length unchanged. In either case a cycle-free shortest path exists. A path with no cycle passes through each vertex at most once. In a graph with V vertices such a path has at most V vertices, hence at most V − 1 edges. This is the reason Bellman-Ford runs V − 1 rounds.

Definition 6.3

If the edges (π[v], v) are taken for every vertex v ≠ s reachable from the source, the result is a tree rooted at s. In this tree the unique path from the root to any vertex is a shortest path to that vertex. This tree is called the shortest-path tree.

The shortest-path tree gathers all shortest paths in a single structure. Since each vertex stores only its own predecessor, all the paths fit in a single array π of size V. To read a path, one starts at the target and follows the π pointers until the source is reached. The vertices obtained this way are in reverse order; to write the path from source to target the order is reversed.

Common mistake

Confusing a negative edge with a negative cycle. A negative edge by itself does not make the shortest path undefined; Bellman-Ford and Floyd-Warshall give correct results on such graphs. The problem is a cycle of negative total weight that is reachable from the source. In an undirected graph, however, even a single negative edge forms a cycle: the path u → v → u carries twice the negative weight.

6.2Dijkstra's algorithm

Dijkstra's algorithm is the most widely used solution of the single-source shortest path problem. Edsger W. Dijkstra devised it in 1956 and published it in 1959 in a short paper of three pages. The algorithm finds the shortest paths from the source to all other vertices. It has a single condition: none of the edge weights may be negative. When this condition holds it is fast, and it is usable in practice even on large road networks.

6.2.1The greedy choice and the water wave

An analogy conveys the idea of the algorithm well. When a stone is thrown into a still lake, the wave spreads in all directions at the same speed. The wave first reaches the point nearest the stone, then the next nearest point. Let us think of the edges as water channels and of the weights as channel lengths. The wave leaving the source reaches the vertices in exactly the order of distance. The wave that first reaches a vertex has come by the shortest path; no wave arriving later could have arrived earlier.

Dijkstra's algorithm imitates the movement of this wave step by step. The vertices are divided into two groups. Vertices whose distance has been finalized are in the set S; the wave has already reached them. The other vertices have only an estimate. At each step, the vertex with the smallest estimate among the unfinalized ones is chosen and finalized. Then the edges leaving this vertex are relaxed, which updates the estimates of the neighbors.

sd=0ad=2bd=4cd=6wave order: s, a, b, c
Figure 6.3: The water wave analogy. The wave leaving the source s reaches the vertices in order of distance: s (0), a (2), b (4), c (6). Dijkstra finalizes the vertices in this order.

An algorithm that at every step takes the option that "looks best right now" and never revises that decision is a greedy algorithm. Dijkstra is greedy: it accepts the distance of the chosen vertex as final and never touches it again. Greedy decisions give wrong results in most problems. In Dijkstra they are correct because the weights are nonnegative. Why this condition is sufficient, and what happens when it is violated, is shown at the end of the section.

6.2.2The steps of the algorithm

The algorithm is summarized in five steps:

  1. Initialization. The distance of the source is set to 0 and that of every other vertex to ∞. The predecessors are undefined and the set of finalized vertices is empty: d[s] = 0, d[v] = ∞, π[v] = undefined, S = ∅.
  2. Selection. Among the unfinalized vertices, the one u with the smallest d value is chosen and added to S. The selection is done by scanning an array or with a priority queue.
  3. Candidate distances. For each not yet finalized neighbor v of u, the candidate distance d[u] + w(u, v) is computed.
  4. Relaxation. If the candidate distance is smaller than d[v], then d[v] and π[v] are updated.
  5. Repeat. Steps 2–4 are repeated until all vertices are finalized or all the remaining vertices have distance ∞. Vertices unreachable from the source keep distance ∞.

Each vertex is chosen once, and at the moment it is chosen its outgoing edges are relaxed once. In a directed graph each edge is considered once overall, in an undirected graph once from each end. All the work of the algorithm consists of these selections and relaxations.

6.2.3Example 1: an undirected graph

The first example is an undirected graph on six vertices; the source is vertex 1. The edges and their weights are: 1–2 (7), 1–3 (9), 1–6 (14), 2–3 (10), 2–4 (15), 3–4 (11), 3–6 (2), 4–5 (6), 5–6 (9). Figure 6.4 shows the initial and final states of the graph side by side.

79141015112691234560∞∞∞∞∞ 7914101511269123456079202011
Figure 6.4: Dijkstra Example 1. Left, the start: the source 1 has distance 0, the others ∞. Right, the end: all vertices are finalized, the red numbers are distances, and the green edges form the shortest-path tree.

The algorithm runs six rounds; in each round one vertex is finalized. Table 6.2 gives the distance estimates after each round. Bold values are the estimates that changed in that round.

Table 6.2: Round-by-round trace of Dijkstra Example 1 (source 1). Each row is the state after the edges of the chosen vertex have been relaxed.
RoundChosen (d)Relaxationsd[1]d[2]d[3]d[4]d[5]d[6]
start——0∞∞∞∞∞
11 (0)2: ∞ → 7; 3: ∞ → 9; 6: ∞ → 14079∞∞14
22 (7)3: 17 ≥ 9, unchanged; 4: ∞ → 2207922∞14
33 (9)4: 22 → 20; 6: 14 → 1107920∞11
46 (11)5: ∞ → 20079202011
54 (20)5: 26 ≥ 20, unchanged079202011
65 (20)no unfinalized neighbor079202011

The rounds in detail. In the first round only the distance of the source is finite; vertex 1 is chosen. Vertex 1 has three neighbors, all with estimate ∞. The edge weights become the new estimates directly: d[2] = 7, d[3] = 9, d[6] = 14. The predecessor of all three is 1.

In the second round the smallest estimate among the unfinalized vertices is 7; vertex 2 is chosen. Vertex 1 is skipped because it is already finalized. The edge 2–3 proposes 7 + 10 = 17; this is larger than 9, so the estimate of 3 is unchanged. The edge 2–4 proposes 7 + 15 = 22, and a path to 4 is found for the first time: d[4] = 22, π[4] = 2.

In the third round 3 is chosen (d = 9). This round is the most instructive step of the example. The edge 3–4 proposes 9 + 11 = 20, which is smaller than the 22 found in the previous round. The estimate of 4 therefore drops to 20 and its predecessor changes from 2 to 3. The edge 3–6 proposes 9 + 2 = 11 and lowers the estimate of 6 from 14. The direct edge from 1 to 6 costs 14; going around through 3 costs 11. A direct edge is not always the shortest path.

In the fourth round the smallest estimate is 11; vertex 6 is chosen. The edge 6–5 gives the first path to 5: 11 + 9 = 20. In the fifth round the estimates of 4 and 5 are equal (20). In a tie the lower-numbered vertex was chosen; 4 is finalized. The edge 4–5 proposes 20 + 6 = 26, which cannot beat 20. In the last round 5 is chosen, and since it has no unfinalized neighbor the algorithm ends.

The final distances are 2: 7, 3: 9, 6: 11, 4: 20, 5: 20. The predecessor array is π[2] = 1, π[3] = 1, π[4] = 3, π[5] = 6, π[6] = 3. These five edges form the shortest-path tree. The shortest path to 5, for example, is found by following the pointers backward: 5 ← 6 ← 3 ← 1. The path is 1 → 3 → 6 → 5, of length 9 + 2 + 9 = 20. The order in which the vertices are finalized is 1, 2, 3, 6, 4, 5; this is the same as the order of the distances from smallest to largest.

Example 6.2

What are the distances if vertex 5 is taken as the source in the same graph?

  1. 5 is chosen (0). Neighbors: 4: ∞ → 6, 6: ∞ → 9.
  2. 4 is chosen (6). 2: 6 + 15 = 21, 3: 6 + 11 = 17.
  3. 6 is chosen (9). 1: 9 + 14 = 23; 3: 9 + 2 = 11 < 17, the estimate drops to 11.
  4. 3 is chosen (11). 1: 11 + 9 = 20 < 23, the estimate drops to 20; 2: 11 + 10 = 21, equal, so unchanged.
  5. 1 is chosen (20), then 2 (21). There are no new relaxations.

Result: d = 1: 20, 2: 21, 3: 11, 4: 6, 5: 0, 6: 9. For example, the path to 3 is 5 → 6 → 3 = 9 + 2 and the path to 2 is 5 → 4 → 2 = 6 + 15.

6.2.4Example 2: a directed graph, the sets Q and S

The second example is a directed graph on five vertices with source 5. The edges are: 5 → 2 (4), 5 → 4 (2), 4 → 2 (1), 4 → 3 (1), 3 → 4 (2), 2 → 1 (3), 1 → 3 (6), 1 → 4 (3). In a directed graph an edge is used only in the direction of the arrow. For example, the edge 2 → 1 allows going from 2 to 1 but not the reverse. The same graph will be used in the Bellman-Ford and Floyd-Warshall examples, so the results of the three algorithms can be compared.

This time the state of the algorithm is followed with two sets. Q is the priority queue of vertices not yet finalized, and keeps the vertices ordered by their d value. S is the list of finalized vertices. At each step the vertex at the head of Q is taken, added to S, and its edges are relaxed.

6332114212345∞∞∞∞0 633211421234563320
Figure 6.5: Dijkstra Example 2. Left, the directed graph and the initial distances (source 5). Right, the final state: only the predecessor edges (green) remain and form the shortest-path tree.
Table 6.3: How the sets Q and S change in Dijkstra Example 2. The vertices in Q are written with their (d, π) values, smallest d first.
StepTaken from QRelaxationsQ (after the step)S
start——5 (0), 1 (∞), 2 (∞), 3 (∞), 4 (∞)∅
15, d = 0(5, 2): ∞ → 4; (5, 4): ∞ → 24 (2, π 5), 2 (4, π 5), 1 (∞), 3 (∞)5
24, d = 2(4, 2): 4 → 3; (4, 3): ∞ → 32 (3, π 4), 3 (3, π 4), 1 (∞)5, 4
32, d = 3(2, 1): ∞ → 63 (3, π 4), 1 (6, π 2)5, 4, 2
43, d = 3(3, 4): 4 is already in S1 (6, π 2)5, 4, 2, 3
51, d = 6(1, 3), (1, 4): both are in Sempty5, 4, 2, 3, 1

The second step needs attention. When 4 is finalized, the edge 4 → 2 proposes 2 + 1 = 3. The estimate of 2 had become 4 in the first step by the direct edge; now it drops to 3. The direct edge from the source to 2 costs 4, while going around through 4 costs 3. In the third step the estimates of 2 and 3 are equal (3); the lower-numbered 2 is taken first. In the fourth and fifth steps there are no new relaxations, because the vertices at the ends of the edges are already finalized.

In the final state the distances and predecessors are as follows:

Table 6.4: Result of Dijkstra Example 2 (source 5).
12345
d63320
π2445/

The green edges give two paths: 5 → 4 → 2 → 1 (length 2 + 1 + 3 = 6) and 5 → 4 → 3 (length 2 + 1 = 3). The edge 5 → 2 does not enter the shortest-path tree, because there is a shorter path to 2 through 4.

6.2.5Pseudocode and lazy deletion

The pseudocode of the algorithm with a priority queue is below. The queue holds (vertex, distance) pairs; the operation pop() returns the pair with the smallest distance.

DIJKSTRA(G, source):
  dist = [ ]; visited = [ ]
  pq = { }
  for each v in V:
    dist[v] = infinity
    visited[v] = 0
  dist[source] = 0
  pq.push(source, 0)
  loop while pq is not empty:
    u = pq.pop()   /* smallest dist */
    if visited[u] == 0:
      visited[u] = 1
      for each (u, v) in G[u]:
        if dist[u] + weight(u, v) < dist[v]:
          dist[v] = dist[u] + weight(u, v)
          pq.push(v, dist[v])
  return dist

The first six lines prepare the arrays: the distance of every vertex is infinity and the visited flag is 0. The distance of the source is set to 0 and the source is added to the queue. The main loop runs until the queue is empty. In each round the record with the smallest distance is removed. If the vertex has not been processed before, it is marked and its neighbors are relaxed. If the distance of a neighbor shrinks, the neighbor is added to the queue with its new distance.

One detail of the code stands out: when the distance of a vertex shrinks, its old record in the queue is not deleted; a new record is added. The same vertex can therefore appear in the queue several times. The old record carries a larger distance, so it leaves the queue later. By the time it comes out, the vertex has already been marked, and the visited check skips it. This technique is called lazy deletion.

The reason for lazy deletion is that Java's PriorityQueue class has no operation that decreases the priority of an item. Removing an arbitrary item from the queue also takes linear time. Adding a new record takes O(log n). The cost is that the queue grows a little: since every relaxation can add a record, at most E records accumulate in the queue. If the path is wanted as well, the assignment prev[v] = u is added to the relaxation.

Common mistake

Skipping the visited check in code with lazy deletion. When an old record comes out, the vertex is processed a second time and its neighbors are relaxed again needlessly. If the weights are nonnegative the result is still correct, but the work increases. The check ensures that each vertex is processed exactly once.

6.2.6Java code and a trace

The Java counterpart of the pseudocode is below. The graph is kept in an adjacency list named adj: adj.get(u) is the list of edges leaving u. Each Edge object has the fields to and weight. The vertices are numbered from 1 to V; the arrays therefore have size V + 1 and index 0 is not used. INF is a constant holding Integer.MAX_VALUE.

void dijkstra(int source) {
  int[] dist = new int[V + 1];
  int[] prev = new int[V + 1];
  boolean[] visited = new boolean[V + 1];
  Arrays.fill(dist, INF);
  dist[source] = 0;
  PriorityQueue<int[]> pq =
    new PriorityQueue<>((a, b) -> a[1] - b[1]);
  pq.add(new int[] { source, 0 });
  while (!pq.isEmpty()) {
    int u = pq.poll()[0];
    if (visited[u]) continue; /* stale entry */
    visited[u] = true;
    for (Edge e : adj.get(u)) {
      int v = e.to, w = e.weight;
      if (!visited[v]
          && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        prev[v] = u;
        pq.add(new int[] { v, dist[v] });
      }
    }
  }
}

The code reads line by line as follows:

  • Lines 2–6: the arrays dist, prev, and visited are created. dist is filled with infinity and that of the source is set to 0. A boolean array starts out false in Java by itself.
  • Lines 7–9: the queue holds int[] pairs: a[0] is the vertex and a[1] its distance at that moment. The comparator (a, b) -> a[1] - b[1] orders the pairs by distance, so poll() gives the pair with the smallest distance. At the start the queue holds only {source, 0}.
  • Lines 11–13: the smallest pair is removed and its vertex taken into u. If the vertex has been processed before, this is a stale entry and is skipped with continue. If not, it is marked; this is the moment the vertex is finalized.
  • Lines 14–21: for every edge leaving u, the neighbor v and the weight w are taken. If the neighbor is not finalized and the path through u is shorter, relaxation is done: the distance and predecessor are updated and a new pair is added to the queue.

The subtraction in the comparator carries an overflow trap. If one of the distances were INF, a[1] - b[1] could overflow and give the wrong sign. In this code only finite distances are added to the queue, so no problem arises. A safer way to write it would be Integer.compare(a[1], b[1]) or Comparator.comparingInt(a -> a[1]).

When the code is run as dijkstra(5) on the graph of Example 2, the queue changes as in Table 6.5. The queue column shows the records in the queue after each operation, in order from smallest to largest.

Table 6.5: Trace of dijkstra(5) (Example 2). The pairs have the form (vertex, distance).
poll()ResultEdges examinedQueue (after)
—start—(5, 0)
(5, 0)5 is finalized5→2: 0 + 4 < ∞, dist[2] = 4; 5→4: 0 + 2 < ∞, dist[4] = 2(4, 2) (2, 4)
(4, 2)4 is finalized4→2: 2 + 1 < 4, dist[2] = 3; 4→3: 2 + 1 < ∞, dist[3] = 3(2, 3) (3, 3) (2, 4)
(2, 3)2 is finalized2→1: 3 + 3 < ∞, dist[1] = 6(3, 3) (2, 4) (1, 6)
(3, 3)3 is finalized3→4: visited[4] = true, condition false(2, 4) (1, 6)
(2, 4)stale entry, skipped—(1, 6)
(1, 6)1 is finalized1→3 and 1→4: both already visitedempty

Lazy deletion is clearly visible in the trace. Vertex 2 entered the queue twice: first as (2, 4), then as (2, 3) when the shorter path was found. The new record comes out first and finalizes 2. The old record (2, 4) comes out at the fifth poll() call; since visited[2] is already true, it is skipped. In all, six poll() calls are made: one for each of the five vertices and one for the stale record. When the loop ends, dist = [6, 3, 3, 2, 0] and prev = [2, 4, 4, 5, –] (indices 1–5); this is the same as the result found by hand.

6.2.7Rebuilding the path

Dijkstra produces the distances and the predecessor array together. The distance array answers "how much?" and the predecessor array "by which path?". The result of Example 2 was π = [2, 4, 4, 5, /]. For target 1 the pointers are followed backward: π[1] = 2, π[2] = 4, π[4] = 5. Vertex 5 is the source, and the trace stops there. The collected vertices are in the order 1, 2, 4, 5, that is, from target to source. When the order is reversed the path is 5 → 4 → 2 → 1, of length 2 + 1 + 3 = 6 = d[1].

The natural way to reverse the order is to use a stack. A stack works by the last-in, first-out (LIFO) principle. Vertices pushed from target to source are popped from source to target.

void printPath(int[] prev, int[] dist,
            int source, int target) {
  if (dist[target] == INF) {   /* unreachable */
    System.out.print("no path"); return;
  }
  Deque<Integer> stack = new ArrayDeque<>();
  for (int v = target; v != source; v = prev[v])
    stack.push(v);         /* from target back */
  stack.push(source);
  while (!stack.isEmpty())
    System.out.print(stack.pop() + " ");
}

The method first checks whether the target is reachable: if dist[target] is still INF, it prints "no path" and returns. Then an empty stack is created; in Java the ArrayDeque class serves as a stack. The for loop starts with v = target. As long as v is not the source, it pushes v onto the stack and moves to the previous vertex. The loop does not push the source, because when v equals the source the condition becomes false. The line after the loop pushes the source separately. The last two lines empty the stack and print the vertices. Table 6.6 is the trace of the call printPath(prev, dist, 5, 1).

6332114212345stack5421← top
Figure 6.6: The state in the call printPath(prev, dist, 5, 1) after the source has been pushed. The source 5 is at the top of the stack and the target 1 at the bottom. The green edges are the shortest path from 5 to 1.
Table 6.6: Trace of printPath(prev, dist, 5, 1); prev = [2, 4, 4, 5, /] (indices 1–5). The top of the stack is written on the left.
StepvActionStackOutput
111 ≠ 5, push(1); v = prev[1] = 2[1]
222 ≠ 5, push(2); v = prev[2] = 4[2, 1]
344 ≠ 5, push(4); v = prev[4] = 5[4, 2, 1]
455 = source, loop ends; push(5)[5, 4, 2, 1]
5–8—four times pop() and print[ ]5 4 2 1

The cost of the method is proportional to the number of edges on the path. Since a path has at most V − 1 edges, the time and the space taken by the stack are O(V). The predecessor array itself takes O(V) space. That all shortest paths can be stored in a single array is a practical consequence of optimal substructure: each path is the path of the previous vertex extended by one edge.

Common mistake

Rebuilding a path without checking reachability. For a target unreachable from the source, the predecessor was never assigned; in Java it stays 0 or holds a sentinel such as −1. The loop can never reach the source: it either spins forever or runs off the end of the array and fails. This is why printPath starts with the check dist[target] == INF.

6.2.8Complexity

The cost of Dijkstra comes from two operations: choosing the vertex with the smallest distance and relaxing the edges. Selection is done V times and relaxation at most E times. The total time depends on the data structure used for these two operations.

  • Array. Distances are kept in an unsorted array. Finding the minimum means scanning the whole array: each selection takes O(V) and V selections take O(V2). Relaxation is a single array write, O(1). The total is O(V2 + E) = O(V2), since in a simple graph E < V2.
  • Binary heap. The priority queue is built with a binary heap. Removing the minimum and inserting a new record take O(log V). There are V removals and at most E insertions: the total is O((V + E) log V). With lazy deletion the queue can hold E records; since log E ≤ log V2 = 2 log V, the bound does not change.
  • Fibonacci heap. In this structure removing the minimum takes amortized O(log V) and decreasing a priority takes amortized O(1). The total is O(E + V log V). This is the best bound in theory, but because the structure has large constants, a binary heap is often faster in practice.
Table 6.7: Cost of Dijkstra by selection structure.
Selection structureSelectionRelaxationTotalSuitable graph
Array (linear scan)V × O(V)E × O(1)O(V²)dense (E ≈ V²)
Binary heapO(log V)O(log V)O((V + E) log V)sparse (E ≪ V²)
Fibonacci heapO(log V) amortizedO(1) amortizedO(E + V log V)best in theory

Which structure is better depends on the density of the graph. In a dense graph the number of edges is of order V2. The heap version then takes O(V2 log V) and is slower than the array version. In a sparse graph the number of edges is of order V and the heap version clearly wins. Road networks are sparse: usually three or four roads leave an intersection.

Example 6.3

A road network has V = 104 intersections and E = 5 · 104 roads. Compare the approximate operation counts of the two versions.

  1. Array version. V2 = 108 operations.
  2. Heap version. V + E = 6 · 104; log2 104 ≈ 13.3, rounded up to 14. The total is about 6 · 104 · 14 ≈ 8.4 · 105 operations.
  3. Comparison. The heap version does about 120 times fewer operations. Because the graph is sparse, the log V cost of the heap at each operation is much cheaper than the array's scanning of all vertices at each selection.

As for memory, the arrays dist, prev, and visited take O(V) space. In the queue with lazy deletion at most E records can accumulate. The total extra memory is O(V + E). In a queue with a decrease-priority operation each vertex is present once and the queue takes O(V) space.

6.2.9Correctness and the negative edge problem

At the moment Dijkstra chooses a vertex, it accepts its distance as final. Why this decision is correct is shown by the following theorem.

Theorem 6.1 (Correctness of Dijkstra)

If all edge weights are nonnegative, then at the moment Dijkstra's algorithm chooses a vertex u and adds it to S, d[u] = δ(s, u).

Suppose the theorem is false and let u be the first vertex for which d[u] > δ(s, u) at the moment it is chosen. Take a shortest path P from the source to u. The path P starts at the source, that is, inside S, and ends at u, outside S. So there is a first vertex on P that lies outside S; call it y, and the vertex before it x. Vertex x was finalized earlier, and by the assumption d[x] = δ(s, x). Since the edge (x, y) was relaxed when x was finalized, d[y] ≤ δ(s, x) + w(x, y) = δ(s, y); that is, d[y] = δ(s, y). Vertex y comes before u on P, and since the weights are nonnegative, δ(s, y) ≤ δ(s, u). From this we get d[y] = δ(s, y) ≤ δ(s, u) < d[u]. But since the algorithm chose u, we must have d[u] ≤ d[y]. Contradiction. □

The key step of the proof is the inequality δ(s, y) ≤ δ(s, u). As the path continues from y to u, its length does not decrease, because every edge added is nonnegative. In short, every path that goes through the outside of S has length at least d[u]; a path can only get longer. A negative edge breaks this assumption. A vertex processed later can open a shorter path to an already finalized vertex through a negative edge. Because Dijkstra never returns to finalized vertices, it never sees that path.

23-2ABC023 23-2ABC023 23-2ABC02 ✗3
Figure 6.7: Dijkstra going wrong on a negative edge. Left: A is finalized; d[B] = 2, d[C] = 3. Middle: the smallest estimate is B's; B is finalized. Right: when C is processed, 3 + (−2) = 1 < 2 is found, but B can no longer be changed.
Example 6.4

In the graph with the edges A → B (2), A → C (3), and C → B (−2), the source is A. Compare the d[B] found by Dijkstra with the true distance.

  1. A is finalized. Relaxations: d[B] = 2, d[C] = 3.
  2. B is chosen. The smallest estimate is B's (2). Dijkstra finalizes B; that is, it decides "there can be no shorter path to B".
  3. C is chosen. The edge C → B proposes 3 + (−2) = 1 < 2. But B is already in S and is not relaxed.
  4. Result. Dijkstra gives d[B] = 2; the true distance is δ(A, B) = 1 (A → C → B). The error is silent: the algorithm produces a wrong number without any warning.

One idea that comes to mind is to remove the negative edges by adding the same constant to all weights. This does not work. Since the constant is added to every edge, paths with many edges are penalized more. If 2 is added to all weights in the example, the path A → B becomes 4 and the path A → C → B becomes 5 + 0 = 5. The direct edge now looks shorter, and the shortest path has changed. Adding a constant preserves the ranking in structures whose number of edges is fixed: for example, every spanning tree has V − 1 edges. In shortest paths the number of edges varies from path to path. If there is a negative edge, the right tool is the Bellman-Ford algorithm.

Common mistake

Treating edges of weight 0 as a problem too. The condition of the theorem is "nonnegative" weights; zero satisfies it. The inequality δ(s, y) ≤ δ(s, u) in the proof also holds with zero-weight edges. Dijkstra fails only on strictly negative edges.

6.3The Bellman-Ford algorithm

Dijkstra is fast but cannot stand a negative edge. The Bellman-Ford algorithm closes this gap. It finds single-source shortest paths, works correctly with negatively weighted edges, and detects negative cycles reachable from the source. The price is speed: Bellman-Ford takes O(V · E) time and is markedly slower than Dijkstra.

The algorithm is named after Richard Bellman (1958) and Lester Ford Jr. (1956). Edward F. Moore published the same method independently in 1959; for this reason some sources call it the Bellman-Ford-Moore algorithm.

6.3.1The idea and the steps

Bellman-Ford finalizes no vertex and selects no vertex. Instead it relaxes all the edges in turn and repeats this scan V − 1 times. One scan is called a round. In each round, the relaxation of an edge lowers the estimate of a vertex. This drop is reflected in the neighbors in later relaxations of the edges leaving that vertex. The improvement thus travels along the path.

This approach is not greedy; it is dynamic programming. Round i builds the shortest paths of at most i edges from the paths of at most i − 1 edges found in the previous round. The four steps of the algorithm are:

  1. Initialization. The source is given distance 0 and the other vertices ∞; the predecessors are undefined.
  2. Rounds. The edges are examined one by one and each is relaxed; this round is repeated V − 1 times. The order of the edges within a round is the same in all rounds. The order does not change the result; it only affects in how many rounds the result is reached.
  3. Propagation. If the distance of a vertex is updated, the distances of its neighbors can be updated in later examinations. The improvement advances at least one edge along the path in every round.
  4. Check. To check for a negative cycle, all edges are examined once more. If some edge still relaxes, there is a negative cycle reachable from the source. If there is no such cycle, no edge relaxes after V − 1 rounds.

Because Bellman-Ford selects no vertex, it does not need an adjacency list either. It is enough to keep the graph as an edge list: each record is a triple (u, v, w). The algorithm reads this list from beginning to end and relaxes each triple.

6.3.2Why V − 1 rounds? Complexity

The origin of the number of rounds rests on a property of shortest paths. If there is no negative cycle, there is a cycle-free shortest path to every vertex, and it has at most V − 1 edges. Each round of the algorithm extends these paths by one more edge.

Theorem 6.2 (Bellman-Ford invariant)

If there is no negative cycle reachable from the source, then at the end of round i, d[v] = δ(s, v) for every vertex v having a shortest path of at most i edges. Accordingly, after V − 1 rounds all distances are correct.

Let the shortest path to v be s = v0, v1, …, vk = v with k ≤ i. We use induction on j. At the start d[v0] = 0 = δ(s, s). Assume that at the end of round j − 1, d[vj−1] = δ(s, vj−1). In round j the edge (vj−1, vj) is relaxed as well. After the relaxation d[vj] ≤ δ(s, vj−1) + w(vj−1, vj) = δ(s, vj); the equality comes from optimal substructure. Since the estimate cannot fall below the distance, d[vj] = δ(s, vj). For j = k ≤ i the claim follows. If there is no negative cycle, the shortest path of every vertex has at most V − 1 edges; taking i = V − 1 gives all distances correct. □

The main idea of the proof is this: in round j the j-th edge of the path is certainly relaxed. The order in which the edges are examined does not matter; an order can only make the work finish earlier. With a favorable order, several edges can improve one after another within one round, and the path can be completed in a single round. In the worst order each round advances only one edge, and all V − 1 rounds are needed.

round 1round 2round 3round 4sv₁v₂v₃v₄At the end of round i, the path with i edges is final
Figure 6.8: In a chain of five vertices the shortest path has four edges. At the end of round i the first i edges of the path are final; four rounds complete the whole path.

The time is easy to compute. Each round examines E edges and each examination takes O(1). V − 1 rounds and one check round make V · E examinations in all: O(V · E). The extra memory is only the distance and predecessor arrays: O(V).

Table 6.8: Running time of Bellman-Ford by density of the graph.
GraphTime
Sparse, E ≈ VO(V²)
Dense, E ≈ V²O(V³)
Best case (early stop)O(E)

The last row of the table comes from a simple improvement. If no d value changes in a round, later rounds cannot change anything either. This is because a round can find a new relaxation only thanks to estimates that changed in the previous round. After a round with no change, the loop can be left. If the edges are in a favorable order, the first round finds everything and the second confirms it: the time drops to O(E).

int[] bellmanFordEarly(int V, List<Edge> edges, int source) {
  int[] dist = new int[V];
  Arrays.fill(dist, INF);
  dist[source] = 0;
  for (int i = 1; i < V; i++) {
    boolean changed = false;
    for (Edge e : edges) {
      int u = e.from, v = e.to, w = e.weight;
      if (dist[u] != INF && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break;   /* nothing changed this round */
  }
  return dist;
}

In the code the flag changed is set to false at the start of each round. Any relaxation in the round sets the flag to true. If the flag is still false when the round ends, break ends the loop. Early stopping does not change the result; it only skips needless rounds. The worst case is still O(V · E), because something may change in every round.

Common mistake

Assuming that Bellman-Ford finishes the job in a single round. This is true if the edge order is lucky, but not in general. In Example 2 with negative edges all five rounds are needed. Also, the check round is a scan separate from the V − 1 rounds; it is not counted among them.

6.3.3Example 1: relaxing edge by edge

The first example is a directed graph on five vertices. The source is s, and the edges are examined in each round in this order: (s, v1) 9, (s, v2) 3, (v1, v2) 6, (v1, v4) 2, (v2, v1) 2, (v2, v3) 1, (v3, v2) 2, (v3, v4) 2.

93622122sv₁v₄v₂v₃0∞∞∞∞ 93622122sv₁v₄v₂v₃05346
Figure 6.9: Bellman-Ford Example 1. Left, the initial state; right, the result. The green edges are the shortest-path tree: s → v2 → v1 (5), s → v2 → v3 → v4 (6).
Table 6.9: The first round of Bellman-Ford Example 1, edge by edge.
EdgeCandidateResultd[v₁]d[v₂]d[v₃]d[v₄]
start——∞∞∞∞
(s, v₁) 90 + 9 = 9 < ∞d[v₁] = 99∞∞∞
(s, v₂) 30 + 3 = 3 < ∞d[v₂] = 393∞∞
(v₁, v₂) 69 + 6 = 15 ≥ 3unchanged93∞∞
(v₁, v₄) 29 + 2 = 11 < ∞d[v₄] = 1193∞11
(v₂, v₁) 23 + 2 = 5 < 9d[v₁] = 553∞11
(v₂, v₃) 13 + 1 = 4 < ∞d[v₃] = 453411
(v₃, v₂) 24 + 2 = 6 ≥ 3unchanged53411
(v₃, v₄) 24 + 2 = 6 < 11d[v₄] = 65346

In the first round six of the eight edges relax. Some estimates change twice within the same round. v1 first becomes 9 by the direct edge, then drops to 5 through v2. v4 first becomes 11, then drops to 6 through v3. This is a case where the edge order helps. The value of v2 was found before the edges leaving it were examined; the improvement therefore spreads along the path within the same round.

In the second round none of the eight edges relaxes. The version with early stopping halts here. The result is d[v1] = 5, d[v2] = 3, d[v3] = 4, d[v4] = 6. Without early stopping, three more rounds and a check round would run in vain. In this order the whole job is finished in a single round.

6.3.4Example 2: negative edges and the worst order

The second example has six vertices and four negative edges. The source is S. The edges are examined in each round in this order: (E, D) −4, (E, A) 4, (C, D) −2, (C, E) 1, (B, C) −2, (A, B) −1, (S, A) 3. This order was chosen on purpose: it arranges the edges of the shortest path from last to first. This is the worst order for Bellman-Ford.

3-1-2-214-4SABCDE0320-31
Figure 6.10: Result of Bellman-Ford Example 2 (source S). The red edge weights are negative. The green edges are the shortest-path tree; the shortest path to D comes through E (−3).
Table 6.10: Round-by-round trace of Bellman-Ford Example 2.
RoundEdges that relaxSABCDE
start—0∞∞∞∞∞
1(S, A): ∞ → 303∞∞∞∞
2(A, B): ∞ → 2032∞∞∞
3(B, C): ∞ → 00320∞∞
4(C, D): ∞ → −2; (C, E): ∞ → 10320−21
5(E, D): −2 → −30320−31
checknone0320−31

In the first round only the edge (S, A) is useful. The start vertices of the other edges in the list are still ∞ at the moment they are examined. For example, the edge (A, B) comes before (S, A) in the list. When it is examined, the estimate of A is still ∞ and the edge is wasted. Each round extends the path by exactly one edge: A, B, C are found in turn. In the fourth round two edges leaving C relax at once. In the fifth round D finds a shorter path through E: 1 + (−4) = −3 < −2. The direct edge C → D gives −2, while the path C → E → D gives 1 − 4 = −3.

All V − 1 = 5 rounds were used. In the check round no edge relaxes; so there is no negative cycle. Indeed, the only cycle in the graph is A → B → C → E → A and its weight is −1 − 2 + 1 + 4 = +2. Although there are negative edges, the cycle is positive.

Example 6.5

If the same edges are examined in reverse order, that is, in the order (S, A), (A, B), (B, C), (C, E), (C, D), (E, A), (E, D), how many rounds does Bellman-Ford with early stopping run?

  1. First round. (S, A): A = 3. Right after, (A, B): B = 2. (B, C): C = 0. (C, E): E = 1. (C, D): D = −2. (E, A) proposes 5 and cannot beat 3. The last edge (E, D): D = −3. Six edges relax.
  2. Second round. No edge relaxes; changed stays false and the loop ends.
  3. Result. Two rounds suffice; the result is the same as in the worst order. The edge order changes not the result but the number of rounds. These two numbers were also confirmed by running the early-stopping code of these notes in Java: 5 rounds in the worst order, 2 rounds in the good order.

6.3.5Example 3: the graph of Dijkstra

The third example is the directed graph of Dijkstra Example 2; the source is again 5. There is no negative edge, so the two algorithms must give the same result. The edges are examined in each round in this order: (1, 3), (1, 4), (2, 1), (3, 4), (4, 2), (4, 3), (5, 2), (5, 4).

Table 6.11: Bellman-Ford Example 3 (source 5). d and π at the end of each round.
RoundEdges that relaxd[1..5]π[1..5]
start—∞, ∞, ∞, ∞, 0/, /, /, /, /
1(5, 2): ∞ → 4; (5, 4): ∞ → 2∞, 4, ∞, 2, 0/, 5, /, 5, /
2(2, 1): ∞ → 7; (4, 2): 4 → 3; (4, 3): ∞ → 37, 3, 3, 2, 02, 4, 4, 5, /
3(2, 1): 7 → 66, 3, 3, 2, 02, 4, 4, 5, /
4none6, 3, 3, 2, 02, 4, 4, 5, /

In the first round the two edges leaving the source are at the end of the list; only they relax. In the second round there are three relaxations. The edge (2, 1) gives the first path to 1: 4 + 3 = 7. Right after, the edge (4, 2) lowers the estimate of 2 to 3. But because (2, 1) comes before (4, 2) in the list, this improvement reaches 1 only in the third round: 3 + 3 = 6. In the fourth round nothing changes.

The result is d = [6, 3, 3, 2, 0] and π = [2, 4, 4, 5, /]. It is exactly the same as the result Dijkstra found. The difference is in the work done. Dijkstra looked at each edge once; Bellman-Ford makes 32 edge examinations in four rounds, and with the check round the number rises to 40.

The check round asks the question d[v] > d[u] + w(u, v) once more for every edge. Table 6.12 shows that on the result of Example 3 the answer to this question is "no" for all eight edges.

Table 6.12: Negative cycle check on the result of Example 3.
Edged[v]d[u] + w(u, v)Result
(1, 3)d[3] = 36 + 6 = 123 ≯ 12 ✓
(1, 4)d[4] = 26 + 3 = 92 ≯ 9 ✓
(2, 1)d[1] = 63 + 3 = 66 ≯ 6 ✓
(3, 4)d[4] = 23 + 2 = 52 ≯ 5 ✓
(4, 2)d[2] = 32 + 1 = 33 ≯ 3 ✓
(4, 3)d[3] = 32 + 1 = 33 ≯ 3 ✓
(5, 2)d[2] = 30 + 4 = 43 ≯ 4 ✓
(5, 4)d[4] = 20 + 2 = 22 ≯ 2 ✓

The edges for which equality holds are notable: (2, 1), (4, 2), (4, 3), and (5, 4). These are exactly the edges of the shortest-path tree. For every edge in the tree d[v] = d[u] + w(u, v), because the value of v came from this edge. For edges outside the tree the inequality is strict.

6.3.6Negative cycle detection

The strength of the check round shows in a graph with a negative cycle. Figure 6.11 is an example with four vertices. There is an edge of weight 2 from the source S to A. The cycle A → B → C → A has weight 1 + (−3) + 1 = −1. The edge order is (S, A), (A, B), (B, C), (C, A).

21-31SABC0-11-2
Figure 6.11: A graph with a negative cycle and the estimates after V − 1 = 3 rounds. The red cycle A → B → C → A has weight −1.
Table 6.13: Estimates at the end of each round in the graph with a negative cycle.
RoundSABC
10130
2002−1
30−11−2

In the first round A first becomes 2 by the edge S → A. Before the round ends, the cycle is traversed: B = 3, C = 0 are found and the edge C → A lowers A to 1. In every later round the three values on the cycle decrease by one. This decrease never stops, because each time the cycle is traversed the path becomes 1 shorter. In a normal graph the values settle in at most V − 1 rounds; here they do not settle.

After V − 1 = 3 rounds, d = [0, −1, 1, −2]. The check round starts with (S, A): 0 + 2 = 2 is not smaller than the value −1 of A. Then comes (A, B): −1 + 1 = 0 < 1. The edge still relaxes; so there is a negative cycle. The shortest path of every vertex on the cycle and every vertex reached from it is undefined (−∞). The d values found are meaningless for these vertices; they merely reflect the round at which the algorithm was stopped.

Theorem 6.3 (Negative cycle check)

If after the V − 1 rounds of Bellman-Ford an edge still relaxes, there is a negative cycle reachable from the source. Conversely, if there is such a cycle, at least one edge relaxes.

The first direction follows from the previous theorem: with no negative cycle, all estimates would be correct after V − 1 rounds and the triangle inequality would allow no edge to relax. For the converse take a reachable negative cycle v0, v1, …, vk = v0 and suppose that no edge relaxes. Then for every edge of the cycle d[vi] ≤ d[vi−1] + w(vi−1, vi) holds. When these k inequalities are added, the sums of d on the left and on the right contain the same vertices and cancel. What remains is 0 ≤ the weight of the cycle. This contradicts the cycle being negative. Because the cycle is reachable from the source, the estimates are finite and the addition is valid. □

Example 6.6

A cycle consists of the edges A → B (3), B → C (−5), and C → A (w), and A is reachable from the source. For which values of the integer w does the check round report a negative cycle?

  1. Cycle weight. 3 + (−5) + w = w − 2.
  2. Negativity condition. w − 2 < 0, that is, w < 2. For integers, w ≤ 1.
  3. Boundary case. At w = 2 the weight of the cycle is 0. Going around the cycle does not shorten the path; there is no negative cycle and the check reports nothing.

6.3.7Pseudocode, Java code, and a trace

The pseudocode of Bellman-Ford has two parts: the outer loop of V − 1 rounds and the single check round that follows.

BELLMAN_FORD(G, source):
  dist = [ ]
  for each v in V:
    dist[v] = infinity
  dist[source] = 0
  loop i = 1 to |V| - 1:
    for each (u, v, weight) in E:
      if dist[u] + weight < dist[v]:
        dist[v] = dist[u] + weight
  for each (u, v, weight) in E:
    if dist[u] + weight < dist[v]:
      error "Graph contains a negative cycle"
  return dist

The outer loop runs |V| − 1 times; the inner loop walks the whole edge list in every round. The last four lines are the check round. The check asks the relaxation condition but makes no assignment; if the condition holds, it reports an error. In the Java counterpart the edges are kept in a list named edges. Each Edge object has the fields from, to, and weight. The vertices are numbered from 0 to V − 1.

void bellmanFord(int source) {
  int[] dist = new int[V];
  int[] prev = new int[V];
  Arrays.fill(dist, INF);
  dist[source] = 0;
  for (int i = 1; i < V; i++) {
    for (Edge e : edges) {
      int u = e.from, v = e.to, w = e.weight;
      if (dist[u] != INF
          && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        prev[v] = u;
      }
    }
  }
  for (Edge e : edges) { /* check */
    int u = e.from, v = e.to, w = e.weight;
    if (dist[u] != INF
        && dist[u] + w < dist[v])
      throw new IllegalStateException(
          "Negative cycle");
  }
}
  • Lines 2–5: the arrays are created, the distances are filled with infinity, and that of the source is set to 0.
  • Line 6: i runs from 1 to V − 1; in all V − 1 rounds.
  • Lines 7–13: for each edge, u, v, and w are taken and relaxation is done. The first part of the condition is dist[u] != INF. If dist[u] is infinite, the addition is never performed.
  • Lines 16–21: the check round asks the same condition. If the condition holds, IllegalStateException is thrown.

The test dist[u] != INF in the condition is not decoration. INF here is Integer.MAX_VALUE, that is, 2,147,483,647. In Java, adding a positive number to it overflows and the result wraps to a negative number: Integer.MAX_VALUE + 3 gives −2,147,483,646. Without the test, an edge leaving an unreached vertex would look "shorter" because of this negative number. In Dijkstra's code this test was not needed, because only vertices with finite distances leave the queue. Bellman-Ford, however, also tries to relax the edges of vertices not yet reached.

Table 6.14 is a trace of the code on a graph with four vertices. The source is 0 and the edge list is in the order (2, 1, −2), (0, 1, 4), (0, 2, 5), (1, 3, 3).

-245301230356
Figure 6.12: The graph of the bellmanFord(0) trace and its result. The shortest path to 1 uses the negative edge 2 → 1: 0 → 2 → 1, of length 5 − 2 = 3.
Table 6.14: Trace of bellmanFord(0).
RoundEdgeConditionResultdist
———start[0, ∞, ∞, ∞]
1(2, 1, −2)dist[2] = ∞skipped[0, ∞, ∞, ∞]
1(0, 1, 4)0 + 4 < ∞dist[1] = 4, prev[1] = 0[0, 4, ∞, ∞]
1(0, 2, 5)0 + 5 < ∞dist[2] = 5, prev[2] = 0[0, 4, 5, ∞]
1(1, 3, 3)4 + 3 < ∞dist[3] = 7, prev[3] = 1[0, 4, 5, 7]
2(2, 1, −2)5 − 2 = 3 < 4dist[1] = 3, prev[1] = 2[0, 3, 5, 7]
2(0, 1, 4)4 ≥ 3unchanged[0, 3, 5, 7]
2(0, 2, 5)5 ≥ 5unchanged[0, 3, 5, 7]
2(1, 3, 3)3 + 3 = 6 < 7dist[3] = 6[0, 3, 5, 6]
3four edgesnone trueunchanged[0, 3, 5, 6]
checkfour edgesnone trueno exception[0, 3, 5, 6]

In the first round the edge (2, 1) is wasted, because it is at the head of the list and the value of 2 is still ∞ when it is examined. In the second round this edge is useful: the negative weight lowers the value of 1 from 4 to 3. At the end of the same round the edge (1, 3) carries this improvement on to 3: from 7 to 6. The third round changes nothing, and the check round throws no exception. The result is [0, 3, 5, 6].

The same code ends differently on a graph with a negative cycle. Let the vertices S, A, B, C be numbered 0, 1, 2, 3. The edges are in the order (0, 1, 2), (1, 2, 1), (2, 3, −3), (3, 1, 1). In the first round all four edges relax: A = 2, B = 3, C = 0, then A = 1. In the second and third rounds three edges relax each time; the values on the cycle fall by one every round. After three rounds dist = [0, −1, 1, −2]. In the check, for the first edge (0, 1), 0 + 2 = 2 is not smaller than −1. For the second edge (1, 2), −1 + 1 = 0 < 1; the condition holds and IllegalStateException("Negative cycle") is thrown.

21-31S0A-1B1C-2check roundnegative cycle!
Figure 6.13: In the check round the edge A → B still relaxes: −1 + 1 = 0 < 1. The code throws the negative-cycle exception.
Common mistake

Skipping the check round and using the result of the V − 1 rounds directly. On a graph with a negative cycle the algorithm still returns an array; the array is full of ordinary numbers and nothing shows that it is wrong. The array [0, −1, 1, −2] in the negative-cycle example is revealed as meaningless only by the check.

6.4The Floyd-Warshall algorithm

Dijkstra and Bellman-Ford work from a single source. Some applications, however, want the distances between all pairs of vertices: the table of distances between all the cities on a map, or the distances of all the routers in a network from one another. The Floyd-Warshall algorithm solves this all-pairs problem in one go. Its code consists of just three nested loops. It works with negative edges and detects negative cycles too.

6.4.1The all-pairs problem

The history of the algorithm is interesting. Bernard Roy in 1959, Stephen Warshall in 1962, and Robert Floyd, also in 1962, published the same idea independently of one another. Warshall's paper computed the transitive closure of a relation, that is, which vertex can reach which. Floyd applied the same structure to shortest paths. The algorithm today bears both their names.

Floyd-Warshall is a dynamic programming algorithm. The results are kept in a V × V matrix D; D[i][j] is the shortest distance from i to j found so far. To rebuild the paths, a second matrix Π is also kept. It is the form of the array π of the single-source algorithms that has a separate row for each source.

The algorithm works in four steps:

  1. Initialization. D is filled with the edge weights: the diagonal D[i][i] = 0, and ∞ where there is no direct edge.
  2. Intermediate vertex. k = 1, 2, …, n are taken in turn. For each k all pairs (i, j) are visited.
  3. Comparison. The length of the path through k, D[i][k] + D[k][j], is computed and compared with the current D[i][j].
  4. Update. If the new path is shorter, the value is written to the matrix and the matrix Π is updated too.

The comparison in the third step is the form of relaxation on pairs of vertices. The paths i ⇝ k and k ⇝ j are joined; if the resulting path is shorter than the known path i ⇝ j, it takes its place.

6.4.2The subproblem and the recurrence

The first job in dynamic programming is to define the subproblem. In Floyd-Warshall the subproblem restricts which intermediate vertices a path may use. The intermediate vertices of a path are its vertices other than the start and the end.

Definition 6.4

D(k)[i][j] is the length of the shortest among the paths i ⇝ j whose intermediate vertices are all chosen from the set {1, 2, …, k}. In D(0) no intermediate vertex is allowed; this matrix contains only the direct edges. In D(n) all vertices may be intermediate; this matrix is the sought result.

How is D(k) found once D(k−1) is known? Consider a shortest path p from i to j whose intermediate vertices come from {1, …, k}. There are two cases.

  • k is not on p. Then all intermediate vertices of p are from {1, …, k − 1} and its length is D(k−1)[i][j].
  • k is on p. If there is no negative cycle, p is a simple path and passes through k only once. The path p splits into the parts i ⇝ k and k ⇝ j. The intermediate vertices of both parts are from {1, …, k − 1}. By optimal substructure each part is shortest on its own. The length is D(k−1)[i][k] + D(k−1)[k][j].

The shortest path is the smaller of these two options:

D(k)[i][j] = min( D(k−1)[i][j], D(k−1)[i][k] + D(k−1)[k][j] )

d[i][j]d[i][k]d[k][j]ikj
Figure 6.14: The Floyd-Warshall recurrence. The dashed arrow is the known path i ⇝ j. The green arrows are the candidate path through k: D[i][k] + D[k][j]. The shorter of the two is kept.

The recurrence says that either k is not on the path or the path passes through k exactly once. The set of intermediate vertices grows by one vertex at each step: first only 1 can be used, then 1 and 2, and finally all vertices. After n steps all possible paths have been taken into account for every pair.

6.4.3Complexity and loop order

The running time can be read off the structure of the code. There are three nested for loops, each running V times. The outermost loop walks over the intermediate vertices (k), the second over the source vertices (i), and the innermost over the target vertices (j). The comparison in the innermost loop takes O(1) and is made V3 times. The time is independent of the number of edges of the graph: Θ(V3). This is a tight bound, with the best and worst cases the same.

The memory is Θ(V2). From the recurrence it might seem that a new matrix is needed for every k. It is not: D can be updated in place. In round k, row k and column k do not change. For D[i][k], for example, the candidate is D[i][k] + D[k][k] = D[i][k] + 0, which cannot beat the current value. All the values D[i][k] and D[k][j] read in this round are therefore the same as their values in D(k−1).

Table 6.15: Options for all-pairs shortest paths.
MethodTime
Floyd-WarshallO(V³)
V × Dijkstra (array)O(V³)
V × Dijkstra (heap)O(V(V + E) log V)
V × Bellman-FordO(V² E)

The table shows that Floyd-Warshall is not always the fastest option. On a sparse graph without negative edges, running heap-based Dijkstra once from every vertex is faster. For V = 200 and E = 800, for example, V3 = 8 · 106, while V(V + E) log2 V ≈ 1.5 · 106. The advantage of Floyd-Warshall lies elsewhere. It works with negative edges, its code is very short, and its constant factor is small. It is a practical choice on dense graphs and for problems up to a few hundred vertices. Running Bellman-Ford V times on a graph with negative edges takes O(V2 E); on a dense graph that is O(V4).

The order of the loops is not arbitrary: k must be outermost. The recurrence builds D(k) from D(k−1). When round k begins, all pairs must have been computed with the intermediate vertices {1, …, k − 1}. If the loops are put in the order i, j, k, each cell (i, j) is computed once, before the other cells are ready.

Example 6.7

What happens if the loops are run in the order i, j, k (k innermost) on the graph of the Floyd-Warshall example below?

  1. The cell 3 ⇝ 1. The correct result is D[3][1] = 6; the path is 3 → 4 → 2 → 1 and uses two intermediate vertices.
  2. The moment of computation. In the wrong order D[3][1] is computed a single time, as the first cell of row 3. At that moment only the direct edges are known: D[3][4] = 2, but D[4][1] is still ∞, because row 4 will be processed later. D[3][2] has not been computed yet either and is ∞.
  3. Result. For no k is D[3][k] + D[k][1] finite, and the cell stays ∞. In an experiment in Python this order found all other cells of the matrix correctly and missed only this one. The number of loops does not change and the time is still Θ(V3); only the correctness of the result changes.

6.4.4Example: the matrices D and Π

The example graph is the directed graph on five vertices used in Dijkstra Example 2 and Bellman-Ford Example 3. This time no source is chosen; all pairs are computed. In the matrix Π, Π[i][j] is the vertex before j on the shortest path from i to j. At the start, if there is a direct edge, Π[i][j] = i; otherwise "/" is written.

6332114212345
Figure 6.15: The graph of the Floyd-Warshall example. The edges are 1 → 3 (6), 1 → 4 (3), 2 → 1 (3), 3 → 4 (2), 4 → 2 (1), 4 → 3 (1), 5 → 2 (4), 5 → 4 (2).
Table 6.16: D(0) and Π(0) (initialization). Row i, column j; each cell shows "D / Π"; "–" is written where Π is undefined.
12345
10 / –∞ / –6 / 13 / 1∞ / –
23 / 20 / –∞ / –∞ / –∞ / –
3∞ / –∞ / –0 / –2 / 3∞ / –
4∞ / –1 / 41 / 40 / –∞ / –
5∞ / –4 / 5∞ / –2 / 50 / –

As intermediate vertices are added in turn, the matrix changes. The cells that change in each round are listed below.

  • k = 1. The only edge into 1 is 2 → 1, so only row 2 can change. 2 ⇝ 3: D[2][1] + D[1][3] = 3 + 6 = 9. 2 ⇝ 4: 3 + 3 = 6. The Π value of both cells becomes Π[1][j] = 1.
  • k = 2. The edges into 2 come from 4 and from 5. 4 ⇝ 1: 1 + 3 = 4. 5 ⇝ 1: 4 + 3 = 7. 5 ⇝ 3: 4 + 9 = 13. The last cell uses the path 2 ⇝ 3 found in the previous round; that path already goes through 1. So the path 5 ⇝ 3 uses two intermediate vertices: 5 → 2 → 1 → 3.
  • k = 3. The only edge leaving 3 is 3 → 4, and no path gets shorter through 3.
  • k = 4. Vertex 4 is the center of the graph; eight cells get shorter: 1 ⇝ 2 (4), 1 ⇝ 3 (6 → 4), 2 ⇝ 3 (9 → 7), 3 ⇝ 1 (6), 3 ⇝ 2 (3), 5 ⇝ 1 (7 → 6), 5 ⇝ 2 (4 → 3), 5 ⇝ 3 (13 → 3). For 5 ⇝ 3, for example, D[5][4] + D[4][3] = 2 + 1 = 3 < 13.
  • k = 5. No edge enters 5; for every i ≠ 5, D[i][5] = ∞. No path gets shorter through 5.
6332114212345
Figure 6.16: The round k = 4. The intermediate vertex 4, with the thick outline, shortens eight paths at once through the edges entering and leaving it.
Table 6.17: Final state D(5) and Π(5); each cell shows "D / Π"; "–" is written where Π is undefined.
12345
10 / –4 / 44 / 43 / 1∞ / –
23 / 20 / –7 / 46 / 1∞ / –
36 / 23 / 40 / –2 / 3∞ / –
44 / 21 / 41 / 40 / –∞ / –
56 / 23 / 43 / 42 / 50 / –

A few results can be read from the final matrix. Column 5 is ∞ from top to bottom except for 5 itself: 5 cannot be reached from any vertex. Row 5 is [6, 3, 3, 2, 0]. This is exactly the distance array that Dijkstra and Bellman-Ford found for source 5. Although Floyd-Warshall runs without choosing a source, each row of the matrix gives the single-source result of the vertex of that row. The diagonal is all 0; there is no negative cycle.

6.4.5Reading a path

Π[i][j] is the vertex before j on the shortest path i ⇝ j. The path is read backward from the target, as in the single-source case. The difference is that the whole reading is done in row i: the vertex before j is Π[i][j], the one before that is Π[i][Π[i][j]], and so on.

Example 6.8

Read the paths 5 ⇝ 1 and 1 ⇝ 2 from the final matrix Π.

  1. 5 ⇝ 1. Read in row 5: Π[5][1] = 2, Π[5][2] = 4, Π[5][4] = 5. Vertex 5 is the source and the reading stops. The path is 5 → 4 → 2 → 1, of length D[5][1] = 6.
  2. 1 ⇝ 2. Read in row 1: Π[1][2] = 4, Π[1][4] = 1. The path is 1 → 4 → 2, of length 3 + 1 = 4 = D[1][2].
  3. Check. 3 ⇝ 1: Π[3][1] = 2, Π[3][2] = 4, Π[3][4] = 3. The path is 3 → 4 → 2 → 1, of length 2 + 1 + 3 = 6 = D[3][1].

The rule for updating Π can be understood from this too. When a shorter path through k is found, Π[i][j] ← Π[k][j] is done. The last part of the new path is the path k ⇝ j. So the vertex before j is the same as the vertex before j on the path k ⇝ j. Writing Π[i][j] ← k would be wrong; k need not be directly joined to j.

6.4.6Pseudocode, Java code, and a trace

The pseudocode has two parts. The first part initializes the matrix.

FLOYD_WARSHALL(G):
  dist = [ ][ ]
  for each u in V:
    for each v in V:
      if u == v:
        dist[u][v] = 0
      else if (u, v) in E:
        dist[u][v] = weight(u, v)
      else:
        dist[u][v] = infinity

The second part is the three nested loops; the diagonal is checked afterward.

  for each k in V:
    for each i in V:
      for each j in V:
        if dist[i][k] + dist[k][j]
             < dist[i][j]:
          dist[i][j] =
            dist[i][k] + dist[k][j]
  for each i in V:
    if dist[i][i] < 0:
      error "Graph contains a negative cycle"
  return dist

The negative-cycle check is simpler than that of Bellman-Ford. A vertex i on a negative cycle finds a path of negative length to itself by going around the cycle. The algorithm computes this path too, and D[i][i] falls below 0. A negative value on the diagonal is therefore the sign of a negative cycle.

In the Java code the matrix is updated in place; no separate copy of D(k) is kept. The matrix prev is a field of the class and initially holds the values prev[i][j] = i.

void floydWarshall(int[][] d) {  /* V x V */
  for (int k = 0; k < V; k++)       /* via */
    for (int i = 0; i < V; i++)     /* from */
      for (int j = 0; j < V; j++)   /* to */
        if (d[i][k] != INF
            && d[k][j] != INF
            && d[i][k] + d[k][j] < d[i][j]) {
          d[i][j] = d[i][k] + d[k][j];
          prev[i][j] = prev[k][j];
        }
  for (int i = 0; i < V; i++)
    if (d[i][i] < 0)
      throw new IllegalStateException(
          "Negative cycle");
}
  • Lines 2–4: three loops; the comments give the role of each loop: via, from, to.
  • Lines 5–7: first it is checked that both parts are finite. Since INF is Integer.MAX_VALUE, the sum of two infinities, or of an infinity and a number, overflows and can wrap to a negative number. The check prevents this overflow.
  • Lines 8–9: the new length is written. prev[i][j] = prev[k][j]: the vertex before j on the new path is the same as on the path k ⇝ j.
  • Lines 11–14: if there is a negative value on the diagonal, an exception is thrown.

The code is traced on a graph with four vertices. The vertices are numbered 0–3. The edges are 0 → 1 (3), 0 → 3 (7), 1 → 0 (8), 1 → 2 (2), 2 → 0 (5), 2 → 3 (1), 3 → 0 (2).

38722510123d001122330356502336012570prev00112233/0123/1230/2301/
Figure 6.17: The graph of the floydWarshall trace and the matrices d and prev after four rounds.
Table 6.18: Cells that change in the floydWarshall trace (in order).
kCellComputationNew dNew prev
0d[1][3]d[1][0] + d[0][3] = 8 + 7 = 15 < ∞15prev[0][3] = 0
0d[2][1]d[2][0] + d[0][1] = 5 + 3 = 8 < ∞8prev[0][1] = 0
0d[3][1]d[3][0] + d[0][1] = 2 + 3 = 5 < ∞5prev[0][1] = 0
1d[0][2]d[0][1] + d[1][2] = 3 + 2 = 5 < ∞5prev[1][2] = 1
1d[3][2]d[3][1] + d[1][2] = 5 + 2 = 7 < ∞7prev[1][2] = 1
2d[0][3]d[0][2] + d[2][3] = 5 + 1 = 6 < 76prev[2][3] = 2
2d[1][0]d[1][2] + d[2][0] = 2 + 5 = 7 < 87prev[2][0] = 2
2d[1][3]d[1][2] + d[2][3] = 2 + 1 = 3 < 153prev[2][3] = 2
3d[1][0]d[1][3] + d[3][0] = 3 + 2 = 5 < 75prev[3][0] = 3
3d[2][0]d[2][3] + d[3][0] = 1 + 2 = 3 < 53prev[3][0] = 3
3d[2][1]d[2][3] + d[3][1] = 1 + 5 = 6 < 86prev[3][1] = 0

Eleven updates are made and eight cells change; some cells get shorter more than once: d[1][0] is 8 at first, falls to 7 at k = 2 and to 5 at k = 3. The final path is 1 → 2 → 3 → 0 and costs 2 + 1 + 2 = 5. d[1][3] becomes 15 at first, then drops to 3. The long path found through 0 gives way to a much shorter one once 2 is added.

After four rounds there is no negative value on the diagonal and no exception is thrown. To read a path, prev is again used. 1 ⇝ 3: prev[1][3] = 2, prev[1][2] = 1. The path is 1 → 2 → 3, of length d[1][3] = 3. The result matrix is d = [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]].

Example 6.9

Find the final D matrix of the graph with the edges 1 → 2 (4), 2 → 3 (1), 1 → 3 (7), and 3 → 1 (−2). Is there a negative cycle?

  1. k = 1. The edge into 1 is 3 → 1. 3 ⇝ 2: −2 + 4 = 2. 3 ⇝ 3: −2 + 7 = 5, greater than 0, unchanged.
  2. k = 2. 1 ⇝ 3: 4 + 1 = 5 < 7. 3 ⇝ 3: 2 + 1 = 3, unchanged.
  3. k = 3. 1 ⇝ 1: 5 + (−2) = 3, unchanged. 2 ⇝ 1: 1 + (−2) = −1. 2 ⇝ 2: 1 + 2 = 3, unchanged.
  4. Result. D = [[0, 4, 5], [−1, 0, 1], [−2, 2, 0]]. The diagonal is entirely 0; the weight of the cycle 1 → 2 → 3 → 1 is 4 + 1 − 2 = 3, and that of 1 → 3 → 1 is 7 − 2 = 5. There is a negative edge but no negative cycle.

The structure of Floyd-Warshall is used beyond shortest paths. If only the information "is there an edge?" is kept instead of weights, "and" is written in place of addition and "or" in place of minimum. The resulting algorithm computes the transitive closure, Warshall's original problem: t[i][j] tells whether there is a path from i to j.

boolean[][] closure(boolean[][] t) {
  int V = t.length;
  for (int k = 0; k < V; k++)
    for (int i = 0; i < V; i++)
      for (int j = 0; j < V; j++)
        t[i][j] = t[i][j] || (t[i][k] && t[k][j]);
  return t;
}

The code again takes Θ(V3) and k again stays outermost. On a graph with four vertices and the edges 0 → 1, 1 → 2, 2 → 0, and 3 → 2, all rows come out as 1110. Vertices 0, 1, and 2 are on the same cycle and reach one another. Vertex 3 also enters this cycle through 2. Vertex 3 itself cannot be reached from any vertex; so the last column is 0 from top to bottom.

6.5A* search

Dijkstra spreads from the source in all directions at the same speed. If we are going to only one goal, most of this spreading is wasted. A Dijkstra looking for the road from Istanbul to Ankara examines the roads to Edirne and Bursa too until it finds Ankara. A* (A star) search reduces this waste. For each vertex it estimates how far is left to the goal and steers the search toward the goal.

Peter Hart, Nils Nilsson, and Bertram Raphael developed A* in 1968 at the Stanford Research Institute. Their aim was to plan the path of a mobile robot. Today it is one of the most widely used search methods for pathfinding of characters in games, in map applications, and in robotics.

6.5.1f = g + h

A* combines the strengths of two searches. Dijkstra (called uniform-cost search in AI textbooks) looks only at the actual cost of arriving from the source. It is therefore correct, but does not know where the goal is. Greedy best-first search, on the other hand, looks only at the estimated cost remaining to the goal. It runs quickly toward the goal but does not care whether the path taken is expensive. A* uses three values for each vertex:

  • g(n), the actual cost: the cost of the path found from the start vertex to n. It is the same as d[n] in Dijkstra.
  • h(n), the heuristic estimate: an estimate of the cost remaining from n to the goal. The straight-line distance on a map and the Manhattan distance on a grid are such estimates.
  • f(n) = g(n) + h(n): the estimated total cost of a solution passing through n. At each step A* expands the vertex with the smallest f value.
Definition 6.5

A heuristic function assigns to each vertex n a number h(n) ≥ 0, an estimate of the cost remaining to the goal. Let h*(n) be the true shortest distance from n to the goal. The heuristic estimate need not be exact; but the more accurate it is, the fewer vertices the search expands.

Table 6.19: Behavior of the search by selection criterion.
Selection criterionAlgorithmBehavior
g(n) onlyDijkstraspreads equally in all directions; correct but expands many vertices
h(n) onlygreedy best-firstruns toward the goal; fast but does not guarantee the shortest path
g(n) + h(n)A*heads for the goal; guarantees the shortest path if h is admissible

The reason the sum works is this. Vertices that look close to the goal have a small h value and move ahead. But if a vertex was reached by an expensive path, g is large and the vertex stays in the background. The two terms balance each other: one answers "how far is left?", the other "what did it cost to get here?"

Example 6.10

There are four vertices in the open list; their (g, h) values are p (4, 7), q (6, 3), r (2, 10), u (8, 2). Which vertex is expanded?

  1. f values. f(p) = 11, f(q) = 9, f(r) = 12, f(u) = 10.
  2. Choice. The smallest f is q's; A* expands q.
  3. Comparison. Dijkstra, looking only at g, would choose r (2); greedy search, looking only at h, would choose u (2). The choice of A* differs from both.

6.5.2The steps of the algorithm

A* uses two lists. The open list is a priority queue holding the vertices that have been discovered but not yet expanded. The closed list holds the expanded vertices. To expand a vertex means to remove it from the open list and examine its neighbors.

  1. The g value of the start vertex is set to 0 and the vertex is added to the open list. The g value of the other vertices is ∞.
  2. The vertex with the smallest f = g + h value is removed from the open list and put in the closed list. The selection criterion is neither g nor h alone, but their sum.
  3. If the removed vertex is the goal, a solution has been found; the path is rebuilt through the predecessor pointers. The goal is finalized not at the moment it is added to the open list but at the moment it is removed from it.
  4. Otherwise, for each neighbor v compute g' = g(u) + w(u, v). If g' is smaller, the values of g, f, and the predecessor are updated and the neighbor is added to the open list. This is exactly the relaxation of Dijkstra. If v is in the closed list and a better g has been found, it is reopened (with a consistent h this never happens).
  5. Return to the second step. If the open list becomes empty, there is no path to the goal.

In the second step the selection is made from the whole open list, not just from the neighbors of the last expanded vertex. This lets A* switch to another branch if the branch it is following becomes expensive. In the graph example this is exactly what happens.

Common mistake

Stopping the search at the moment the goal is added to the open list. At the moment of addition the g value of the goal is only an upper bound; a cheaper path may be waiting in the open list. In Dijkstra too, the distance of a vertex is finalized when it leaves the queue, not when it enters. A* applies the same rule to the goal.

6.5.3Properties of the heuristic function

Whether A* finds the shortest path depends on the heuristic. Two properties matter.

Definition 6.6

If h(n) ≤ h*(n) for every n, then h is admissible: it never exceeds the true remaining cost.

If h(u) ≤ w(u, v) + h(v) for every edge (u, v) and h(goal) = 0, then h is consistent.

Theorem 6.4 (Optimality of A*)

If h is admissible, the path A* has found when it removes the goal from the open list is a shortest path.

Suppose the goal t is removed via a path with g(t) > h*(s), that is, a path that is not shortest. Let P be a shortest path from s to t. Before t is removed, one of the vertices on P, say n, is in the open list with a correct g(n); this is shown by a simple induction starting from the first expansion of s. Because h is admissible, f(n) = g(n) + h(n) ≤ g(n) + h*(n) = h*(s). At the goal h(t) = 0, so f(t) = g(t) > h*(s) ≥ f(n). At the moment t is chosen, the open list contains n, which has a smaller f value. Since A* always picks the vertex with the smallest f, this is impossible. Contradiction. □

Consistency is a stronger property. A consistent heuristic is always admissible. With a consistent h, when a vertex enters the closed list its g value is final and the vertex is never reopened. This is the exact counterpart of finalization in Dijkstra. Indeed, with a consistent h, A* is Dijkstra running on a graph with edge weights w(u, v) − h(u) + h(v) ≥ 0. With an admissible but inconsistent heuristic, a vertex can later be reopened through a cheaper path.

Example 6.11

Chain graph s → a → t; w(s, a) = 2, w(a, t) = 3. Two heuristics are to be examined: (1) h(s) = 4, h(a) = 4, h(t) = 0; (2) h(s) = 4, h(a) = 1, h(t) = 0.

  1. True remaining costs. h*(s) = 5, h*(a) = 3, h*(t) = 0.
  2. First heuristic. h(a) = 4 > 3 = h*(a): it exceeds the true remaining cost. It is not admissible.
  3. Second heuristic, admissibility. 4 ≤ 5, 1 ≤ 3, 0 ≤ 0: it is admissible.
  4. Second heuristic, consistency. On the edge (s, a) we ask whether h(s) ≤ w(s, a) + h(a): 4 ≤ 2 + 1 = 3 is false. The heuristic is admissible but not consistent. In going from s to a the estimate drops by 3 at once, more than the edge of 2 units.

In searches on a grid, the common heuristics are chosen by the movement rule:

  • 4-direction movement (up, down, right, left; each step 1): the Manhattan distance |Δx| + |Δy|. Each step reduces this sum by at most 1; hence h ≤ h*.
  • 8-direction movement (straight step 10, diagonal step 14): the octile distance 14 · min(|Δx|, |Δy|) + 10 · (max − min). First go diagonally as far as possible, then straight. The number 14 is 10 · √2 ≈ 14.14 rounded to an integer.
  • Free plane: the Euclidean distance √(Δx2 + Δy2), that is, the straight line.

The Manhattan distance is not admissible with 8-direction movement. A diagonal step reduces the sum |Δx| + |Δy| by 2 but costs only 1 (or 1.4). For a goal with Δx = Δy = 3, for example, the Manhattan distance is 6. On an 8-direction grid with every step costing 1, the true remaining cost is only 3, with three diagonal steps. The heuristic doubles the true value.

The quality of a heuristic is understood through two extreme cases. If h = 0 is taken, f = g and A* turns into exactly Dijkstra. This heuristic is admissible but gives the search no direction. If h = h* (a perfect estimate) is taken, every vertex on the shortest path has f equal to h*(s), while vertices off the path have larger f. If ties are broken suitably, only the vertices on the path are expanded. A heuristic with h > h*, that is, one that overestimates, can speed up the search but removes the guarantee of a shortest path.

6.5.4Complexity

The cost of A* is described through the search tree. Let b be the branching factor, that is, the average number of neighbors of a vertex. Let d be the depth of the goal, that is, the number of steps in the solution. In the worst case the search expands all vertices down to depth d. Time and memory are therefore O(bd). This bound is that of a useless heuristic, for example h = 0. With a perfect estimate the search is linear in the path length: only the d vertices on the path are expanded.

On a finite graph with a consistent h, A* does no more work than Dijkstra. Each vertex is expanded at most once and the total time with a binary heap is O((V + E) log V). In practice a good heuristic stays far below this bound, because the vertices in the direction opposite the goal are never opened.

The real weak point of A* is memory. The open and closed lists grow with the search and can fill memory on large maps. Memory-bounded variants have been developed to solve this problem. IDA* (iterative deepening A*) repeats depth-first search with a rising f limit and keeps only the current path in memory. SMA* (simplified memory-bounded A*) drops the worst-looking vertices from the list when memory fills up.

6.5.5Example: A* on a graph

The example is an undirected graph; the start is s and the goal is t. The edges are s–a 1.5; s–d 2; a–b 2; b–c 3; c–t 4; d–e 3; e–t 2. The heuristic values are h(s) = 5, h(a) = 4, h(b) = 2, h(c) = 4, h(d) = 4.5, h(e) = 2, h(t) = 0.

1,5234232sdaebcth=4,5h=4h=2h=2h=4to 1,5234232sdaebcth=4,5h=4h=2h=2h=4to
Figure 6.18: The A* example. Left, after the first expansion: s is closed, a and d are open. Right, the final state: the shortest path is s → d → e → t (7). Vertex c is never expanded.
Table 6.20: Open and closed lists in the A* example. In the open list the f values are sorted from smallest to largest.
StepExpanded (f)Opened / updatedOpen list: vertex (g, h, f)Closed
1s (5)a: g = 1,5; d: g = 2a (1,5; 4; 5,5), d (2; 4,5; 6,5)s
2a (5,5)b: g = 3,5b (3,5; 2; 5,5), d (2; 4,5; 6,5)s, a
3b (5,5)c: g = 6,5d (2; 4,5; 6,5), c (6,5; 4; 10,5)s, a, b
4d (6,5)e: g = 5e (5; 2; 7), c (6,5; 4; 10,5)s, a, b, d
5e (7)t: g = 7t (7; 0; 7), c (6,5; 4; 10,5)s, a, b, d, e
6t (7)goal removed, stopc (6,5; 4; 10,5)s, a, b, d, e, t

The search first heads for the upper branch. The f value of a is smallest at 5.5, and then b also moves ahead with 5.5. When b is expanded, c is opened, but the g value of c has risen to 6.5 and f(c) = 10.5. This branch has become expensive. In the open list the smallest f is now that of d (6.5), and the search switches to the lower branch. This switch is a consequence of the selection being made from the whole open list. From d, e is opened (f = 7), and from e, t is opened (g = 7, f = 7).

When t is removed from the open list, the search stops. The shortest path is s → d → e → t with cost 2 + 3 + 2 = 7. The upper branch s → a → b → c → t costs 1.5 + 2 + 3 + 4 = 10.5. Vertex c has been opened but never expanded. Six of the seven vertices have been expanded. In the same graph Dijkstra would expand the vertices in order of distance: s, a, d, b, e, c, t; since the distance of c (6.5) is smaller than that of t (7), it would expand c too.

6.5.6Java code and a trace

The Java code of A* is very similar to that of Dijkstra. The differences are in two places: the queue is ordered by g + h and the search stops when the goal is removed. g, h, and parent are class fields; g and h are double arrays. adj[u] is the edge list of u, and each edge has the fields v (neighbor) and w (weight).

double aStar(int s, int t) {
  Arrays.fill(g, INF); g[s] = 0;
  Queue<Integer> open = new PriorityQueue<>(
    Comparator.comparingDouble(v -> g[v] + h[v]));
  open.add(s);
  while (!open.isEmpty()) {
    int u = open.poll();      /* smallest f */
    if (u == t) return g[t];  /* goal */
    for (Edge e : adj[u])
      if (g[u] + e.w < g[e.v]) {
        g[e.v] = g[u] + e.w; parent[e.v] = u;
        open.remove(e.v); open.add(e.v);
      }
  }
  return INF;
}
  • Line 2: all g values are set to infinity and that of the start to 0.
  • Lines 3–5: the open list is a priority queue. The comparator orders each vertex v by the value g[v] + h[v]. At the start only s is in it.
  • Lines 7–8: the vertex with the smallest f is removed. If it is the goal, g[t] is returned. The stopping condition is checked at removal time.
  • Lines 9–13: each edge is relaxed. If g decreases, the predecessor is written to parent. The vertex is first removed from the queue and then added again.
  • Line 15: if the queue empties, there is no path to the goal.

The pair remove and add on line 12 is important. The comparator reads the array g[v]. If g[v] changes while a vertex is in the queue, the heap's ordering is broken, because the heap placed the vertex according to its old value. Removing the vertex and adding it again puts it in the right place for its new value. PriorityQueue.remove(Object) takes linear time; for large graphs lazy deletion, as in Dijkstra, is preferred.

When the code is run on the graph of the A* example, the poll() order is s (f = 5), a (5.5), b (5.5), d (6.5), e (7), t (7). The g updates at each step are the same as the values in Table 6.20. At the sixth call the goal is removed and return g[t] returns 7. Reading the parent array backward gives t ← e ← d ← s, that is, s → d → e → t. Vertex c stays in the open list with f = 10.5 and is never removed.

1,5234232sh=5 g=0ah=4 g=1,5bh=2 g=3,5ch=4 g=6,5dh=4,5 g=2eh=2 g=5th=0 g=7
Figure 6.19: The final state of the aStar(s, t) trace. The vertex labels show h and the g found; the boxed t is the goal that was removed.
Example 6.12

A directed graph: s → a (1), a → t (9), s → b (2), b → c (2), c → t (2). The heuristic: h(s) = 5, h(a) = 1, h(b) = 4, h(c) = 2, h(t) = 0. Compare greedy best-first search with A*.

  1. Greedy search. After s, a (h = 1) looks more attractive than b (h = 4). From a, t is opened (h = 0) and chosen at once. The path is s → a → t, cost 10.
  2. A*. f(a) = 1 + 1 = 2, f(b) = 2 + 4 = 6. a is expanded; t is opened with g = 10, f = 10. Then b (6) and c (f = 4 + 2 = 6) are expanded; from c the g value of t drops to 6. t (f = 6) is removed: the path is s → b → c → t, cost 6.
  3. Result. This h is admissible, so A* finds the shortest path. Greedy search is fast, but because it ignores g it picks the expensive path.

6.5.7Example: around a wall on a grid

The most familiar use of A* is on grid maps. In the example there is a grid of 8 columns and 7 rows. The start is A and the goal is B. Between them stands a wall in the shape of an inverted L. Movement is 8-directional: a straight step costs 10 and a diagonal step 14. The heuristic is the octile distance and ignores the walls. A and B differ by 3 columns and 3 rows; h(A) = 3 · 14 = 42.

In the figures each cell carries three numbers: g at top left, h at top right, and f in the middle.

B142842103848144862103848A105262144862105262145670 B244468442468342054242448142842103848144862483482303060203454103848A105262344074244468144862105262145670
Figure 6.20: A* on a grid. Left, the first expansion: the eight neighbors of A are opened; the smallest f is 42 (straight toward B, the cell below the wall). Right, after the fourth expansion: the cells below the wall are tried first, with f = 42 … 54.

The search first heads for the cells right below the wall, in the direction of B. Because the heuristic cannot see the wall, these cells look the most promising. The f values of the expanded cells, in order, are:

42, 42, 48, 48, 48, 54, 54, 60, 62, 62, 62, 62, 68, 68, 68, 68, 68, 68

The values never decrease. This is a property of a consistent heuristic: the f values of expanded vertices form a nondecreasing sequence. The path below the wall is blocked; to get over the wall one must go around, either from the right or from the left. The cost of going around is not in the estimate, and f rises step by step. At the thirteenth expansion f = 68 is reached and the search spreads to both sides of the wall. At the seventeenth expansion the path going around the right side of the wall reaches B; B enters the open list with f = 68.

721082621476522476483482524496680B 68581068482068383068344074385088582482244468285482542882442468342054242448142842103848144862245882583896403474303060203454103848A105262206282444488344074244468144862105262145670246690285482245882206282246690
Figure 6.21: The final state when B is removed. The blue cells are the path found: one step up from A, diagonally up and right, diagonally up and left, and three steps left over the top of the wall. The cost is 2 · 14 + 4 · 10 = 68.

B is removed at the eighteenth expansion and the search stops. The cost of the path found is 68: two diagonal steps (28) and four straight steps (40). Of the eighteen expansions, eleven are closed (pink) cells and seven are cells on the path. The cheapest path going around the left of the wall costs 96. A* has opened the cells of the leftmost column in that direction but has expanded none of them. A few cells in the corners of the grid have never been opened at all.

In the example, diagonal steps can graze the corner of the wall. Both diagonal steps of the path pass the corner of a wall cell. In many games this "corner cutting" is forbidden: a diagonal step is allowed only if the two straight neighbors beside it are also free. Such a rule can change the result of the search, but it does not change how A* works.

Common mistake

Using the Manhattan distance on an 8-direction grid. The heuristic exceeds the true remaining cost, and A* takes the first path it finds to be the shortest. The search seems to speed up, but a shorter diagonal path can be missed. Octile distance should be used with 8 directions, Euclidean distance in the free plane.

6.6Shortest paths in unweighted graphs: BFS

If all edge weights are equal, for example all 1, the length of a path equals its number of edges. The shortest path is the path with the fewest edges. In this special case heavy algorithms are not needed. Breadth-first search (BFS) solves the problem in linear time.

BFS visits the vertices layer by layer, in order of distance from the source. First come the neighbors of the source (distance 1), then their unvisited neighbors (distance 2), and so on. When a vertex v is first found from u, d[v] = d[u] + 1 and π[v] = u are written. A vertex has reached its shortest distance the moment it is first found; paths found later cannot be shorter.

The relation of BFS to Dijkstra is clear. Dijkstra chooses the vertex with the smallest distance with a priority queue. When the weights are equal, vertices enter the queue in order of distance. An ordinary queue working by the first-in, first-out (FIFO) principle already preserves this order, and the priority queue is no longer needed. Since queue operations are O(1), the total time is O(V + E); the log V factor of the heap disappears.

0172345601112233
Figure 6.22: BFS on an unweighted graph. The numbers are the BFS level, that is, the number of edges from the source 0. The green edges are the BFS tree. The shortest path from 0 to 6 is 0 → 2 → 4 → 6 (3 edges).

In the graph in the figure the edges are 0–1, 0–2, 0–7, 1–2, 2–3, 2–4, 3–5, 4–6, and 5–6. The neighbors 1, 2, and 7 of 0 are at level one. The neighbors 3 and 4 of 2 are at level two. The neighbor 5 of 3 and the neighbor 6 of 4 are at level three. Another path to 6 is 0 → 2 → 3 → 5 → 6, but it has four edges. BFS finds 6 first from 4 and writes π[6] = 4; the path through 5 is seen later and changes nothing.

BFS also suffices if all edge weights are the same constant c. The distances are c times the levels. In the same graph with all edges 5, for example, the distance of 6 is 3 · 5 = 15. If the weights differ, BFS errs; the path with the fewest edges may not be the shortest path.

When there is a single goal, a variant of BFS is faster. Bidirectional search starts BFS at the same time from the source and from the goal. When the two waves meet in the middle, the search stops. In a search with branching factor b and goal depth d, one-directional BFS expands about bd vertices. Bidirectional search expands about 2 · bd/2. For b = 10 and d = 6 this means two thousand vertices instead of a million.

6.7Comparison and choice of algorithm

The five algorithms of this chapter use the same basic operation, relaxation. Their differences lie in which problem they solve, which restrictions they accept, and how long they take. Table 6.21 gathers these differences in one table.

Table 6.21: Comparison of the shortest-path algorithms.
AlgorithmProblemNegative edgesNegative cyclesTimeMethod
BFSsingle source, unweighted——O(V + E)layer by layer
Dijkstrasingle sourcenonoO(V²) / O((V + E) log V)greedy
Bellman-Fordsingle sourceyesdetectsO(V · E)repeated relaxation (DP)
Floyd-Warshallall pairsyesdetectsΘ(V³)dynamic programming
A*single pairnonoworst case O(bd)heuristic + greedy

The choice is made with a few questions:

  1. Is the graph unweighted? BFS is enough.
  2. Are all weights zero or positive? Use Dijkstra. If there is a single goal and a good heuristic, A* expands fewer vertices.
  3. Are there negative edges? Use Bellman-Ford; this also checks for negative cycles.
  4. Are all pairs wanted and is V small? Use Floyd-Warshall.
Example 6.13

Choose an algorithm for four situations.

  1. The fewest intermediaries between two people in a social network. The edges are unweighted: BFS, O(V + E).
  2. The shortest route between two addresses on a map. Lengths are positive, there is a single goal, and straight-line distance is an admissible heuristic: A*.
  3. V = 1000, E = 5000, some edges negative. Dijkstra is unreliable; use Bellman-Ford. About V · E = 1000 · 5000 = 5 · 106 relaxation attempts are made.
  4. All distances between 200 cities. All pairs are wanted and V is small: Floyd-Warshall, 2003 = 8 · 106 operations.
Example 6.14

A directed graph: A → B 4, A → C 2, C → B 1, B → D 5, C → D 8, C → E 10, D → E 3; source A. Run Dijkstra and Bellman-Ford on this graph.

  1. Dijkstra. A is finalized: B = 4, C = 2. C is finalized: B improves to 2 + 1 = 3; D = 10, E = 12. B is finalized: D drops to 3 + 5 = 8. D is finalized: E drops to 8 + 3 = 11. Finally E is finalized. The order is A, C, B, D, E; the distances are A: 0, B: 3, C: 2, D: 8, E: 11.
  2. Path. π[E] = D, π[D] = B, π[B] = C, π[C] = A. The path is A → C → B → D → E, of length 2 + 1 + 5 + 3 = 11.
  3. Bellman-Ford, alphabetical edge order (A → B, A → C, B → D, C → B, C → D, C → E, D → E). In round 1 five relaxations occur: B = 4, C = 2, D = 9, B = 3, E = 12. In round 2 two relaxations occur: D = 8, E = 11. In rounds 3 and 4 nothing changes; early stopping is possible. The result is the same as Dijkstra's.

6.8Common mistakes

The most important of the mistakes given in boxes throughout the chapter are collected here.

  • Dijkstra with a negative edge. A shorter path can later open to a finalized vertex; the result comes out wrong without any warning. With a negative edge Bellman-Ford is needed. Adding a constant to the weights is not a solution either; paths with many edges are penalized more.
  • The overflow of ∞ + w. Integer.MAX_VALUE + w wraps to a negative number and looks "shorter". For this reason d[u] != INF is checked before adding. In Floyd-Warshall both parts must be checked.
  • The loop order of Floyd-Warshall. The loop over intermediate vertices k must be outermost. The order i, j, k leaves some cells at ∞ or larger than necessary.
  • The number of rounds. In Bellman-Ford all V − 1 rounds may be needed; the job may not finish in a single round. The check round is separate from these rounds.
  • Stopping at the goal in A*. One stops when the goal is removed from the list, not when it is added to the open list. An h that overestimates can miss the shortest path.
  • Negative weight on an undirected edge. An undirected negative edge is by itself a negative cycle through the path u → v → u. If an undirected graph has a negative weight, the shortest path is undefined.
  • Printing a path to an unreachable target. The predecessor array never reaches the source. First check that the distance is finite.

6.9Summary

  • In a weighted graph the length of a path is the sum of its edge weights. The shortest path need not be the path with the fewest edges. δ(s, v) is the length of the shortest path from s to v.
  • There are three kinds of problem: single-source (Dijkstra, Bellman-Ford, BFS), all-pairs (Floyd-Warshall), and single-pair (A*).
  • The operation common to all the algorithms is relaxation: if d[u] + w(u, v) < d[v], then d[v] and π[v] are updated. An estimate only decreases and never falls below the true distance.
  • Every part of a shortest path is itself shortest (optimal substructure). If there is no negative cycle, a shortest path has at most V − 1 edges. If a negative cycle is reachable, the shortest path is undefined.
  • Dijkstra finalizes the vertex with the smallest estimate and relaxes its neighbors. Weights must be nonnegative. It takes O(V2) with an array and O((V + E) log V) with a binary heap. A queue with lazy deletion skips stale records by the visited check.
  • Bellman-Ford relaxes all edges for V − 1 rounds. It works with negative edges; an edge that still relaxes in round V shows a negative cycle reachable from the source. The time is O(V · E); with early stopping the best case is O(E).
  • Floyd-Warshall applies the recurrence D[i][j] = min(D[i][j], D[i][k] + D[k][j]) with k outermost. The time is Θ(V3) and the memory Θ(V2). D[i][i] < 0 shows a negative cycle.
  • A* expands the vertex with the smallest f = g + h. With an admissible h it finds the shortest path; with a consistent h each vertex is expanded once. If h = 0 is taken, A* turns into Dijkstra.
  • In an unweighted graph BFS finds the path with the fewest edges in O(V + E) time.
  • Paths are read backward from the target through the π (or Π) pointers; together the pointers form the shortest-path tree.

6.10Key terms

  • shortest path
  • distance
  • weighted graph
  • single-source shortest paths
  • all-pairs shortest paths
  • relaxation
  • optimal substructure
  • negative cycle
  • Dijkstra's algorithm
  • priority queue
  • greedy algorithm
  • Bellman-Ford algorithm
  • dynamic programming
  • Floyd-Warshall algorithm
  • A* search
  • heuristic
  • admissible heuristic
  • breadth-first search (BFS)

6.11Test Yourself

  1. A directed graph: s → a 2, s → b 6, a → b 3, a → c 7, b → c 1, c → t 2, b → t 8. Source s. In what order does Dijkstra finalize the vertices? What are the final distances and the path from s to t?

    Answer

    The order is s, a, b, c, t. a = 2; b is first 6, then drops to 2 + 3 = 5 through a; c = 5 + 1 = 6 (it would be 9 through a); t = 6 + 2 = 8 (it would be 13 directly from b). The path is s → a → b → c → t, of length 8.

  2. Roughly how many operations do array-based Dijkstra and binary-heap Dijkstra make on a graph with V = 105 and E = 4 · 105? How many relaxation attempts does Bellman-Ford make?

    Answer

    Array: V2 = 1010. Heap: (V + E) log2 V ≈ 5 · 105 · 16.6 ≈ 8.3 · 106. Bellman-Ford: V · E = 4 · 1010. Because the graph is sparse, heap-based Dijkstra is by far the fastest.

  3. A chain graph s → a → b → c with all weights 1. How many rounds does Bellman-Ford with early stopping run if it examines the edges (a) in the order (b, c), (a, b), (s, a), (b) in the order (s, a), (a, b), (b, c)?

    Answer

    (a) Each round advances only one edge: a is found in round 1, b in round 2, c in round 3. All V − 1 = 3 rounds are used. (b) All three are found in round 1; in round 2 nothing changes and the algorithm stops: 2 rounds. The result in both is [0, 1, 2, 3].

  4. Floyd-Warshall is run on the graph with the edges 0 → 1 (4), 1 → 2 (2), 2 → 0 (1). Which cell changes after round k = 0? What is the final D matrix?

    Answer

    k = 0: the only edge into 0 is 2 → 0; D[2][1] = 1 + 4 = 5. k = 1: D[0][2] = 4 + 2 = 6. k = 2: D[1][0] = 2 + 1 = 3. The final matrix is [[0, 4, 6], [3, 0, 2], [1, 5, 0]]. The diagonal is 0; the weight of the cycle is 7.

  5. Floyd-Warshall is run on the graph with the edges 0 → 1 (1), 1 → 2 (−2), 2 → 0 (−1), 0 → 2 (4). What is seen on the diagonal? What does the code do?

    Answer

    The weight of the cycle 0 → 1 → 2 → 0 is 1 − 2 − 1 = −2. At the end of the algorithm negative values appear on the diagonal (−2, −2, and −4 with in-place updating). The check d[i][i] < 0 is true on the first row and IllegalStateException("Negative cycle") is thrown. The other values of the matrix are meaningless.

  6. From the final matrix Π of the Floyd-Warshall example, which is the path 3 ⇝ 1? Does the length of the path agree with D[3][1]?

    Answer

    In row 3: Π[3][1] = 2, Π[3][2] = 4, Π[3][4] = 3. The path is 3 → 4 → 2 → 1, of length 2 + 1 + 3 = 6 = D[3][1].

  7. A chain s → a → t with w(s, a) = 2, w(a, t) = 5. Is the heuristic h(s) = 6, h(a) = 5, h(t) = 0 admissible? Is it consistent?

    Answer

    The true remaining costs are h*(s) = 7, h*(a) = 5, h*(t) = 0. 6 ≤ 7, 5 ≤ 5: admissible. Consistency: h(s) = 6 ≤ 2 + 5 = 7 and h(a) = 5 ≤ 5 + 0; both hold, so the heuristic is consistent.

  8. Can BFS be used on a graph in which all edge weights are 5? What is the distance of 6 in the graph of the BFS example?

    Answer

    It can. When all weights are equal, the shortest path is again the path with the fewest edges; the distance is 5 times the BFS level. Vertex 6 is at level three: 3 · 5 = 15.

  9. In the Java code of Dijkstra the comparator is (a, b) -> a[1] - b[1]. What could happen if a record with distance Integer.MAX_VALUE were added to the queue?

    Answer

    The subtraction could overflow. For example, Integer.MAX_VALUE - (-1) wraps to a negative number and the comparator reports the wrong order. In the code of these notes only finite distances are added to the queue, so no problem arises. The safe way to write it is Integer.compare(a[1], b[1]).

  10. Dijkstra is modified to also keep the number of shortest paths to each vertex. In the graph with the edges s → a 1, s → b 1, a → c 1, b → c 1, c → t 1, s → t 3, a → t 2, what is count[t]?

    Answer

    d[t] = 3 and four paths have this length: s → t, s → a → t, s → a → c → t, s → b → c → t. The algorithm finds count[c] = 2; to t come 1 path from s, 1 from a, and 2 from c: count[t] = 4. The rule: when a shorter path is found the count starts over (count[v] = count[u]); when a path of equal length is found it is added (count[v] += count[u]).

The rule in the last question is implemented by the following code. The code does the selection by scanning an array and has been tried out in Java.

long[] countPaths(int V, List<List<int[]>> adj, int source, int[] dist) {
  long[] count = new long[V];
  boolean[] done = new boolean[V];
  Arrays.fill(dist, INF);
  dist[source] = 0; count[source] = 1;
  for (int round = 0; round < V; round++) {
    int u = -1;
    for (int x = 0; x < V; x++)
      if (!done[x] && dist[x] != INF && (u == -1 || dist[x] < dist[u])) u = x;
    if (u == -1) break;
    done[u] = true;
    for (int[] e : adj.get(u)) {
      int v = e[0], w = e[1];
      if (dist[u] + w < dist[v]) {        /* shorter path: restart count */
        dist[v] = dist[u] + w;
        count[v] = count[u];
      } else if (dist[u] + w == dist[v]) { /* new paths of equal length */
        count[v] += count[u];
      }
    }
  }
  return count;
}

The rule relies on the weights being positive. When a vertex is finalized, all shortest paths into it have come from vertices of smaller distance, that is, from vertices finalized earlier. Therefore count[u] is complete the moment u is finalized, and the correct value is passed on to the neighbors.

6.12Further reading

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 22 and 23: gives the properties of relaxation, the correctness proofs of Dijkstra and Bellman-Ford, Floyd-Warshall, and Johnson's algorithm for sparse graphs in detail.
  • R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 4.4: presents Java code for the shortest-path algorithms, Dijkstra with an indexed priority queue, and queue-based Bellman-Ford.
  • S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach (4th ed., 2020), Chapter 3: treats A*, admissible and consistent heuristics, IDA*, and memory-bounded search variants from the viewpoint of artificial intelligence.
  • E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs" (1959): the original three-page paper of the algorithm; the same paper also solves the minimum spanning tree problem.

6.13References

  1. R. Bellman, "On a Routing Problem", Quarterly of Applied Mathematics 16, 1958.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapters 22–23).
  3. E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik 1, 1959.
  4. R. W. Floyd, "Algorithm 97: Shortest Path", Communications of the ACM 5(6), 1962.
  5. P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics 4(2), 1968.
  6. S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2020.
  7. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 4.4: Shortest Paths).
  8. S. Warshall, "A Theorem on Boolean Matrices", Journal of the ACM 9(1), 1962.

Related pages: Chapter 6 slides · © Sercan Külcü. All rights reserved.