Shortest Path Algorithms
BACK: Minimum Spanning Trees
Suppose I wanted to know the fastest possible road to get from one place to another. I could spin around the block 50 times before I decide to actually leave the neighborhood and go to Costco–that would technically be a path to get to Costco. But often, I want to minimize the cost to get to Costco (gas may be cheap there, but it’s still moolah!). Shortest path algorithms are used everywhere. What is the path that minimizes the cost to get from point A to point B? I’ve mentioned before–almost every problem we have, we try to make it into a graph problem.
But there are several different cases I need to consider when picking an algorithm: Are there negative weights? Is it a DAG? Are there cycles? Are the cycles nonnegative? Are we just finding the single pair between A and B or do we also want A to B, C, D, and E? The different algorithms that I cover handle these different case.
But first, we need to initialize the problems. The pseudocode to initialize these algorithms is to set each node’s predecessor to \(NULL\) and to also set the cost to get there as \(\infty\). We will also set the cost of the starting node equal to 0. (\(\text{Initialize-Single-Source}\) pseudocode on page 648).
We also need to understand the idea of \(\text{Relaxing}\) (in more ways than one). Basically, if the current Vertex \(u.cost +\) Edge \(uv.weight\) < \(v.cost\), then \(v.cost\) = \(u.cost + uv.weight\) and we also need to change the parent of that \(v\) to be \(u\). I still have no idea why this concept is called ‘relax,’ and it confuses me every time I come back to this book.
Djikstra’s Algorithm
Djikstra’s is always the way to go (not really but everyone uses it) and generates the shortest path from \(s\) to all of the other nodes. It is a greedy algorithm that assumes that all weights are nonnegative–the greedy idea is super interesting here. The pseudocode is on page 658.
We start by initializing the problem with a minimum priority queue with the starting vertex inside of it. The pseudocode also includes the set \(S\) which keeps track of which vertices we for sure know the shortest path to. For the first iteration, since we are extracting out vertices from the minimum queue, we know that this has to be the shortest path to that vertex. i.e: If there was a shorter path to \(s\rightarrow y\) (\(s\rightarrow t \rightarrow y\)), we would have extracted \(t\) from the first iteration before \(y\). (Triangle inequality?)
We relax every child that we run into and after we extract any vertex from the minimum queue, we know that we have found the minimum cost to get there. Repeat until the queue is empty.
The runtime for Djikstras is \(O(V^2 + E) = O(V^2)\), but this also depends on how we represent the graph. Using a fibonacci heap will save you some time.
Bellman-Ford
Unlike Djikstra’s, Bellman Ford is not a greedy algorithm. Because it does not make the same assumption that Djikstra’s does, Bellman Ford is able to handle graphs with negative edges, but can NOT handle graphs with non-negative edges. The pseudocode is on page 651 and it solves the same problem as Djikstras: what is the shortest cost to get from every other vertex from the starting vertex \(s\)?
What is a non-negative edge? Suppose I’m in at a toll bridge and it costs $4 to get past. However, I travel down a road, which costs $2 to go down. But I meet a friendly guy who will pay me $100 (-100) to go down a certain road that leads back to the toll bridge.
Why would I not just keep going around in circles in order to find “the shortest path”? I could make infinity money if I just keep looping around endlessly!
Because of this idea, Bellman Ford does not handle graphs with these kinds of cycles. Before it terminates, it will check for these negative cycles and return a boolean value of whether it was able to successfully complete or not (i.e. the graph contained a negative cycle or not).
As the video mentions, Bellman-Ford runs for \(V - 1\) iterations. As we can see from the iterative process that he goes over, updating it any more than \(V-1\) times doesn’t yield any new \(\text{Relax}\) changes.
Floyd-Warshall
Floyd-Warshall solves the all-pair shortest path problem with negative edges, where its output will tell you what the shortest path to each vertex is for EVERY vertex (i.e: A to B, C, D, E and B to A, C, D, E and C to …). It uses the ideas of dynamic programming and stores everything into a large matrix, but to be honest is pretty useless.
The pseudocode is on 698 and it’s a pain in the butt to run it by hand. On top of that, if you have no negative weights, there is a better solution: running Djikstra’s V times for every Vertex. The running time for Floyd-Warshall is \(O(V^3)\), which is the same or grows faster than running Djikstra’s for each vertex. If you do have negative weights, you could run Bellman-Ford for every vertex.
Johnson
Johnson’s Algorithm also solves the same problem as Floyd-Warshall (all-pair shortest path), but it handles the problem differently. It seeks to handle the negative edges by somehow transforming the negative edges into nonnegative ones. The pseudocode is on page 704, but the big ideas are as following:
We start by adding a new vertex \(s\) to the graph, which connects to every other vertex with an edge cost of 0. Afterwards, we will run Bellman-Ford on this “new” graph, with \(s\) as our starting vertex. As we can see in step (a), we have done this and found the single-source shortest path from \(s\) to every other vertex. Because we ran Bellman-Ford here, we also check for negative cycles.
In any case, the result for every vertex should be a nonpositive number for each vertex. In step (b), we reweight all of the edges to the following: \(C_e' = C_e + p_u - p_v\) (New Cost of \(e\) = Original Cost of \(e\) + Path Cost of \(u\) - Path Cost of \(v\)). So for edge \(1-2\), we have \(4 = 3 + 0 - (-1)\) and for edge \(3-2\) we have \(0 = 4 + -5 - (-1)\).
After reweighting, we can apply Djikstra’s \(V\) times for each vertex because all edge costs are now nonnegative.
More references:
We’re almost done; just one more section!