To find the shortest path in a weighted graph, we can use an algorithm known as Dijkstra’s algorithm, named after the Dutch computer scientist Edsger W. Dijkstra. Dijkstra’s algorithm works similar to breadth-first search: starting at a particular node \(S\) of a weighted graph, it visits all reachable nodes in the order of
increasing distance from \(S\).
To illustrate how Dijkstra’s algorithm works, consider the simple weighted graph shown in Fig. 8.7. It’s easy to determine the shortest paths from S to all the other nodes by hand: The shortest path
to B is \(\text {S}\to \text {B}\) (length 1), the one to C is \(\text {S}\to \text {B}\to \text {C}\) (length 4), the one to A is \(\text {S}\to \text {B}\to \text {A}\) (length 5), and the one to D is \(\text {S}\to \text {B}\to \text {D}\)
(length 6). When traversing this graph starting at S, Dijkstra’s algorithm visits the nodes in this order: S, B, C, A, D.
Figure 8.7 A simple weighted graph.
The main idea behind Dijkstra’s algorithm is to maintain a list of nodes that have already been discovered but still need to be explored in more detail. You will recall that this is the same idea that underlies breadth-first search, but in the absence of edge weights we could simply visit the nodes in the order
they were discovered and store the list of unexplored nodes in a queue. This is no longer possible when the edges are weighted because the order in which we discover nodes doesn’t always match the order in which we need to visit them. For example, in Fig. 8.7 node A is discovered immediately since it is a direct neighbor of the starting node S, but it is visited after B and C because it is farther away from S.
We can solve this problem by replacing the queue used in breadth-first search with a list of nodes that we keep sorted by their distance from the start. Figure 8.8 illustrates how
we can use such a data structure to traverse the graph from Fig. 8.7. Initially, the list of unexplored nodes contains just the starting node S whose distance is obviously 0. In the first step, we visit S and add its two
neighbors to the unexplored list, sorted by their distance from S. In each of the following steps, unexplored is updated by removing the first node and adding all or some of its neighbors. In Step 2 we reach node B, which tells us that that B’s distance from S
is 1. Three other nodes are reachable from B: node A at total distance 9, node C at total distance 4, and node D at total distance 6. We discard the new path to A since we already discovered a shorter route in the first step, but we add the new nodes
C and D to unexplored. In Step 3 we visit C and discover yet another path that leads to A. This path has a total weight of \(5\) and is therefore shorter than the existing path to A, so we update unexplored with the new distance. The last two
steps visit A and D and add no new nodes to unexplored.
.
Figure 8.8 Dijkstra’s algorithm visits all nodes that are reachable from the start S in the order of increasing distance. To do this, the algorithm maintains a list of unexplored nodes sorted by their distance from S and visits the nearest unexplored
node in each step.
The performance of Dijkstra’s algorithm depends on the data structure that is used to store the list of unexplored nodes. The data structure that is most commonly used for this purpose is the priority queue, which associates a numeric priority with every element of the queue. Priority queues typically provide the following operations:
• \(\attribir {pq}{isEmpty}()\): Return true if there are no elements in the queue.
• \(\attribir {pq}{insert}(u, p)\): Add a new element \(u\) with associated priority \(p\) to the queue.
• \(\attribir {pq}{extractMin}()\): Remove the element with the smallest associated priority from pq and return it.
• \(\attribir {pq}{decreaseKey}(u, p)\): For an element \(u\) that is already in the queue, reduce its priority to \(p\) and adjust its position in the queue.
Algorithm 8.1
Dijkstra’s algorithm. Given a weighted graph \(G\) with nonnegative weights and a single node \(S\), determine the shortest paths from \(S\) to every reachable node in \(G\). After the algorithm has completed, the dist field of a node indicates
its distance from \(S\) and the pred field is the predecessor along the corresponding shortest path.
Using such a priority queue, we can describe Dijkstra’s algorithm as shown in Algorithm 8.1. We assume that every node has two fields that can be used to store the algorithm’s output: \(n.\Id
{dist}\) for the shortest distance from the start \(S\) to \(n\) and \(n.\Id {pred}\) for the predecessor along the shortest path. At the start of the algorithm, we reset the dist and pred fields of all nodes and then initialize the algorithm by
adding \(S\) to the priority queue and setting its dist field to 0. We then repeatedly remove the nearest unexplored node from pq and inspect all its neighbors. For each neighbor \(v\) we distinguish between two conditions. If we haven’t encountered \(v\) before (its
dist field is \(\infty \)) we use \(\mathrm {insert}()\) to add it to pq. Otherwise, if the new path to \(v\) via \(u\) is shorter than the one we have found before, we update its dist and pred fields and use \(\mathrm {decreaseKey}()\) to move \(v\)
closer to the front of pq.
After the algorithm has finished, we can examine the dist and pred fields to find the shortest path from \(S\) to each node in the graph. If \(n.\Id {dist}\) is \(\infty \), the node hasn’t been reached and no shortest path exists. Otherwise, \(n.\Id {dist}\) is the length of
the shortest path, and we can find the nodes on this path by following the pred nodes back to the start.
Implementing Dijkstra’s Algorithm
Let’s now turn to the problem of implementing Dijkstra’s algorithm. Similar to the version of breadth-first search we discussed in Section 7.3, we will store the shortest paths from the starting node as a
tree of path segments that link to their predecessors. As before, we define a record that implements the BasicPath interface, but since we are now dealing with paths in a weighted graph, we add a
new integer field totalWeight that stores the path’s weighted length from the start. The resulting WeightedPath type is shown in Listing 8.17.
Listing 8.17ch8 / WeightedPath
// Data type for representing paths through weighted graphs.
public record WeightedPath<N>(
N node, WeightedPath<N> predecessor, int totalWeight)
implements BasicPath<N> {
}
We implement Dijkstra’s algorithm not as a static function but as a class that stores the algorithm’s state in a handful of fields (Listing 8.18):
• The graph field is the graph that is being traversed.
• The dist field corresponds to the dist attribute in Algorithm 8.1 and holds the weighted distance of every visited node from the start.
• The unexplored field replaces the pq data structure in Algorithm 8.1 and maintains a priority queue of incomplete paths that still need to be explored.
• The result field is a table that stores the shortest paths to every visited node.
Listing 8.18ch8 / Dijkstra
// Implementation of Dijkstra's algorithm for weighted graphs.
public class Dijkstra<N> {
private final WeightedGraph<N> graph;
private final Map<N, Integer> dist = new HashMap<>();
private final PriorityQueue<WeightedPath<N>> unexplored;
private final Map<N, WeightedPath<N>> result = new HashMap<>();
// ...
}
In the pseudocode of Algorithm 8.1, most of the algorithm’s state was stored in two attributes dist and pred that we associated with each node — why do we use
different data structures here? One reason is technical: If we want to implement the algorithm generically, we cannot assume that the node type N contains two fields dist and link that we can use for bookkeeping. The only requirement is that we can use N as the key type in a hash table.
The constructor Dijkstra() in Listing 8.19 takes a graph and a starting node as arguments and initializes the algorithm’s data
structures. The priority queue for unexplored is initialized using a comparator object that determines how the elements are sorted. Here, the expression
returns a function that compares two WeightedPath objects by their totalWeight fields, which ensures that the path segment at the front of unexplored is the one with the smallest value of totalWeight. In Algorithm 8.1 we used a loop to reset the dist and pred fields of all nodes before the start of the algorithm; this isn’t necessary here because dist and
result are initialized to empty hash tables.
The main part of Dijkstra’s algorithm repeats the following three steps as long as there are entries in unexplored:
1. Extract the nearest unexplored node from the queue.
2. Check whether it has any undiscovered neighbors or neighbors that can now be reached more quickly.
3. Update the priority queue if that’s the case.
These steps are performed by the nextNode() method shown in Listing 8.20. The implementation differs from the description
in Algorithm 8.1 in one crucial respect: If a shorter path to a previously discovered node is found (newDist < oldDist), we don’t update the priority of the existing entry in unexplored but instead add a new entry. This change is necessary because the PriorityQueue class doesn’t support the decreaseKey() operation.
Listing 8.20ch8 / Dijkstra
// Process and return the nearest unexplored node.
private N nextNode() {
while (!unexplored.isEmpty()) {
WeightedPath<N> path = unexplored.remove();
N node = path.node();
if (result.putIfAbsent(node, path) != null)
continue; // skip nodes that were reached before
for (var edge : graph.edges(node)) {
int newDist = path.totalWeight() + edge.weight();
int oldDist = dist.getOrDefault(edge.target(), -1);
if (oldDist == -1 || newDist < oldDist) {
dist.put(edge.target(), newDist);
unexplored.add(
new WeightedPath<>(edge.target(), path, newDist));
}
}
return node;
}
return null;
}
As a result, unexplored can now contain multiple paths to the same node. The following if statement at the start of the loop ensures that no node is visited more than once:
if (result.putIfAbsent(node, path) != null)
continue; // skip nodes that were reached before
The call to putIfAbsent() stores the shortest path to the current node in result, but only the first time this node is encountered. If result already contains an entry for node, we
know that the current path must be longer than the one discovered earlier and ignore it.
Finally, we implement two variations of Dijkstra’s algorithm using nextNode() (Listing 8.21). The first is traverse(), which visits every node that is reachable from start and returns a map that contains the shortest path to each of them. The second method shortestPath() works similarly but uses an additional Predicate to stop at the first node that satisfies a certain condition.
The method returns either the path to this node or null if no suitable node was found.
Listing 8.21ch8 / Dijkstra
// Visit all nodes reachable from 'start' and return the
// shortest paths.
public static <N> Map<N, WeightedPath<N>> traverse(
WeightedGraph<N> graph, N start) {
var dijkstra = new Dijkstra<>(graph, start);
while (dijkstra.nextNode() != null) {
}
return dijkstra.result;
}
// Find the shortest path from 'start' to the nearest node
// that satisfies 'condition'.
public static <N> WeightedPath<N> shortestPath(
WeightedGraph<N> graph, N start, Predicate<N> condition) {
var dijkstra = new Dijkstra<>(graph, start);
while (true) {
N node = dijkstra.nextNode();
if (node == null)
return null;
if (condition.test(node))
return dijkstra.result.get(node);
}
}
With Dijkstra’s algorithm in hand, we can now finally solve our original problem of finding the solution of a given Sokoban level that requires the fewest number of steps. To do this, we first construct the weighted push graph and then search for
the shortest path from the starting configuration to any game state that solves the level:
WeightedPath<GameState> path = Dijkstra.shortestPath(
new WeightedPushGraph(level),
new GameState(level),
gameState -> gameState.allCratesOnGoals(level));
System.out.printf("Pushes: %d%n", path.length());
System.out.printf("Steps: %d%n", path.totalWeight());
System.out.println(SokobanSolver.compressMoves(
SokobanSolver.computeSteps(level, path.toNodeList())));
This outputs the following solution, which requires 230 steps and again 97 pushes — that’s 32 fewer steps than in the solution we found in Section 8.4:
As before, we have added line breaks to the output to indicate when a crate has reached the goal area. It’s worth trying this solution yourself: Even though most steps are obvious and either move the worker (or a crate) from one side of the level to the other, the final steps on each line, which arrange the
crates in the goal area, are surprisingly elegant.
Exercises
Exercise 8.8.A square in a Sokoban level is called dead if there is no way to push a crate from this square to any of the goals.
a) Consider the level shown in the following image, which has two goals in the upper right. Which squares in this level are dead?
b) Develop an algorithm that computes all dead positions in a Sokoban level.
