Simplifying our scenario allowed us to use a simple and fast algorithm, BFS, to obtain an approximated shortest path for our deliveries. While our simplification works well for modern city centers, such as for downtown San Francisco, it can’t be applied to more generic scenarios. If we need to optimize deliveries for a wider area in San Francisco, or in other cities lacking this regular road structure, approximating distances with the number of blocks traveled doesn’t work well anymore.
If we move from San Francisco (or Manhattan) to Dublin’s center, for instance, as figure 14.16 shows, streets don’t have a regular layout anymore, and blocks can greatly vary in size and shape, so we need to take into account the actual distance between each pair of intersections, which won’t be their Manhattan distance anymore.
1. Differences with BFS
Like BFS, Dijkstra’s algorithm takes a graph and a source vertex as input (optionally a goal vertex as well), and computes the minimum distance from the source to the goal (or equivalently, with the same asymptotic running time, to all the other vertices in the graph). Differently than for BFS, though, in Dijkstra’s algorithm the distance between two vertices is measured in terms of edges’ weight. Consider figure 14.17, which shows a directed, weighted graph that models the map shown in figure 14.16.
In this context, the minimum distance between two vertices u and v is the minimum sum, across all paths from u to v, of the weights of edges in the path. If there is no such path, that is, if there is no way to go from u to v, then the distance between them is considered to be infinite.
Figure 14.18 shows, on a simpler example graph, how Dijkstra’s algorithm works. It is similar to BFS, with two main differences:
- The metric used is the sum of weights instead of path lengths.
- Consequently, the container needs to be used to keep track of the next vertices to be visited: we can’t make do with a plain queue anymore; we need a priority queue.
Everything else, the logic of the algorithm and the auxiliary data used, is similar to BFS. That’s very convenient for us because we can rewrite this algorithm from listing 14.2 with minimal changes. If you think that this similarity is a coincidence, though, hold your breath untill section 14.5.
2. Implementation
Listing 14.6 describes Dijkstra’s algorithm in detail. Comparing it to listing 14.2, you can see how it resembles the BFS algorithm, so much so that we can use the same algorithm shown in listing 14.3 to reconstruct the shortest path for Dijkstra’s as well. Nonetheless, we need to be even more careful about performance in this case.
3. Analysis
While in BFS each vertex was added to the (plain) queue and never updated, Dijks- tra’s algorithm uses a priority queue to keep track of the closest discovered vertices, and it’s possible that the priority[1] of a vertex changes after it has already been added to the queue.
This is due to a fundamental difference. BFS only uses the number of edges traversed as a metric, and if we use the edge’s weight instead, then it’s possible that a path including more edges has a lower weight than another path including fewer edges. For instance, looking at figure 14.18, there are two paths between v1 and v2; the path v1^v3^v2 only traverses 2 edges, but its total weight is 8, while the other path, v1^v3^v5^v2 has length 3, but its total weight is just 5. The second path is longer, and visits one more vertex between v3 and v2, so the distance to v2 will be initially set to 8 (when v3 is visited), and then updated to 5 when it’s v5’s turn to be visited.
Because of this behavior, every time a new vertex is visited, potentially all its neighbors’ priorities can be updated.
In turn, this influences the asymptotic performance of Dijkstra’s algorithm, which depends on how efficiently this “update priority” operation can be implemented. In detail, for Dijkstra’s algorithm, we can implement the priority queue as
- An array (sorted or unsorted, as described in appendix C)
- A heap
- A Fibonacci heap
The running time using an array for the priority queue is going to be O(|E|*|V|), because each vertex will require O(|V|) operations to update priority or to adjust the queue after extraction.
With the remaining two choices, the running time is O(|V|*log(|V|) + |E|*DQ(|V|)) where
- |V| is the number of vertices on the graph.
- |E| is the number of edges.
- DQ(|v|) is the (average) running time of each “priority update” operation.
Table 14.2 summarizes the running time of Dijkstra’s algorithm, relating it to the implementation of priority queue used.
The best theoretical result is obtained with a Fibonacci heap, for which the amortized time to decrease the priority of an element is O(1). However, this data structure is complicated to implement and inefficient in practice, so our best bet is using heaps. As we saw in section 2.9, d-way heaps allow us to have a more efficient implementation in practice.
4. Shortest route for deliveries
So far in this section, we’ve discussed how Dijkstra’s algorithm works, how we can implement it, and its performance.
Now there is only one thing left to tackle: how we apply this algorithm to our example and find the shortest route to deliver an order to a customer.
The good news is that it’s actually straightforward. Once we have created the graph in figure 14.17, we can just apply the algorithm to it (or to the example in figure 14.10, exactly how we did for BFS) and reconstruct the shortest path.
The result for this section’s example is shown in figure 14.19, where we computed and showed the shortest distance from the source vertex (vS) to every other vertex.
Notice that there are some edges, drawn with a thin dotted line, that don’t belong to any shortest path, while the shortest path to our destination, vG, is highlighted with thick dashed lines.
This example is perfect to illustrate the need of algorithms such as Dijkstra’s because there are two paths between vS and vG that add up almost to the same distance, and our intuition would likely go for the longest one, because it looks more linear.
One final consideration: As we mentioned, applying the algorithm was straightforward, but only because of one property of this graph. It doesn’t have any edge with negative weight. Any such edge would, in fact, violate the assumption behind the algorithm: that if we expand the frontier of visited vertices by choosing the closest unvisited vertex at each iteration, then at the time a vertex is visited, we know its minimum distance from start.
This happens because Dijkstra’s algorithm (like BFS) is a greedy algorithm, a kind of algorithm that can find the solution to a problem by making locally optimal choices. In fact, to decide which vertex to visit next, we only need to take into account the outgoing edges of the vertices we’ve already visited. Greedy algorithms can only be applied to certain problems: having negative edges makes a problem unfit to be solved with any greedy algorithm, because locally-optimal choices won’t be possible anymore.
Negative-weight edges might seem counterintuitive, but they are actually quite common. If we measure distances using the gas consumed to travel between two vertices, and the goal is to not end up with an empty tank, then an edge corresponding to a road with a gas station could have a negative weight. Likewise, if we associate a cost to the gas, then an edge that allows us to perform a second delivery or a pick-up could have negative cost because we could earn extra money if we travel it.
To cope with negative edges, we need to use Bellman-Ford’s algorithm, an ingenious algorithm that uses the dynamic programming technique to derive a solution that takes into account negative-weight edges. Bellman-Ford’s algorithm is more expensive to run than Dijkstra’s; its running time is O(|V|*|E|). Although it can be applied to a broader set of graphs, it too has some limitations: it can’t work with graphs with negative-weight cycles (at the same time, though, it can be used as a test to find such cycles).
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)