Dynamic Programming applied to Graphs
Dynamic programming is “an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states.” When it’s applied to graphs, we can solve for the shortest paths with one source or shortest paths for every pair. Let’s take a look at what kind of problems dynamic programming can help us solve.
1. Bellman-Ford
It is an algorithm to find the shortest paths from a single source. There is another algorithm that does the same thing, which is Dijkstra’s algorithm. Then how is Bellman-Ford different from Dijkstra’s? Although Dijkstra, being a greedy algorithm, is faster than Bellman-Ford’s, it fails if there are negative edges in graphs. Therefore, Bellman-Ford is used to calculate the shortest path from a single source. It uses a very elegant dynamic programming solution.
It uses the concept of relaxation, which is decreasing the distance of the node by adding the edge length and the distance of the previous node. More details can be found here. My article will focus more on the dynamic programming aspect.
Recurrence: Bellman-Ford builds recurrence on the number of edges.
The important concept here is that a graph uses at most n-1 edges, and we can come up with the following expression.
Let OPT(i, v) be the cost of a shortest s-v path using at most i edges.
Then, OPT(i, v) = 0, if i is 0 and v = s. It takes no edge to reach yourself.
OPT(i, v) = ∞, if i = 0 and v is not s. If a node is not a neighbor of v, then there is no way to get to that node immediately, so it’s ∞.
Other than that, we have two important cases:
(1) OPT(i, v) uses less than i edges. It is the left diagram above. Then we don’t need to add weight when we move along the graph. Instead, we can just move forward to examine the next edge. “v” is the target node we want to get to. Since we didn’t find the target yet, we can keep “v” the way it is and just use less edges to look for the target node.
(2) OPT(i, v) uses i edges. It is represented by the right diagram above. Then we need to figure out what is the weight of that edge and move onto the next edge.
But there’s a catch. Since there might be multiple maths with i edges, so we need to take a minimum out of those.
Please note that even if we need to take minimum of those 2 different cases. Why? Isn’t OPT(i-1, v) the best case? Don’t forget that we are taking negative edges into consideration, so either one of those cases can lead to a smaller path. Therefore, we need to compute both of them and take the minimum of those two.
Doesn’t this remind you of 0–1 Knapsack problem? Once can think of the nodes as the size of the backpack and the edges as the items. For each node, you are taking an edge or not taking and carrying that you had previously. That’s why they both have very similar recurrence relations.
Now let’s think about how many subproblems there are. Assuming we have n number of nodes, we have n choices for v and n-1 choices for i. It means we need n by n matrix to keep track of our progress.
Space: O(n²)
What is the time complexity? It takes O(degree of v) to calculate minimum of OPT(i-1, x) + w(x, v). You need to do that for every n for the entire row of i, so it’s O(M). And it’s repeated for every row, so it’s O(NM)
Running time: O(NM)
Here’ s the pseudocode.
Let’s run an example for a better understanding.
The above-mentioned matrix can be constructed like this:
An important question arises at this point. Can we do better with the space? Do we really need all that huge chunk of a matrix? As we can note from the recurrence relation as well as the way the matrix was filled in, we just need to look at the previous row. So we only need two rows of that matrix to keep track of our progress. Actually, we can just use an array to represent the progress, had we changed the recurrence relation a little bit, by dropping the index i. We can do this, since every node will calculate the minimum with the same number of edges and we just need to save results for each node. It is the same idea as unbounded knapsack problem. For details: https://medium.com/@logicdevildotcom/knapsack-problems-18b2714e0737
The pseudocode now changes to
The one on the left is the changed one and the right is the original one. If you compare them side by side, they are doing the same thing logically. The difference is that while the original algorithm checks every node in every i-th iteration, the modified version checks only the neighboring nodes.
The pink array indicates the array that we use in the new DP solution and the grey indicates the inner for loop of the pseudo code.
Running time: O(NM)
Space: O(N)
Why does relaxation order not matter?
For the example above, there are 3 nodes, so two iterations of relaxation can be done. If the relaxation happens backwards starting from the node b and then to node a, the first iteration would yield b: infinity, a: 2. Then the second iteration is b:5, a:2. In the first iteration b can’t be updated, since only one edge was used, only the a node, which is one edge away from it, can be updated. The second iteration is when two edges were used from the source to anywhere, so b can finally be updated. In the first iteration, b simply couldn’t be updated since a was not ready.
Then how about we take a look at the forward update? In the first iteration, it would be a: 2 and b: 5. The second iteration is a: 2 and b: 5 again. Going forward lets all the successive nodes be ready with updated distances, so more iterations do not change value. But then one might wonder what if I am doing 100 iterations for 101 nodes, and I was doing the forward update. Would it be possible that everything was updated in the first iteration and there was no change up to the 99th iteration and all of a sudden there was a node that decreased in its distance at the 100th iteration? No, it is not possible, because the forward update does not cause change after the 1st iteration unless there is a negative cycle.
Can we detect a negative cycle?
Yes! We just need to run the algorithm for one more iteration. Instead of having the iteration of |N|- 1 times, we can do it |N| times. If the value changes in the n-th iteration, it means there is a negative edge cycle. If we relax the edges backwards, the maximum time it would take is n-1 times. if we relax the edges forward, we just need one iteration and no change would be found in the next iterations. Therefore, if there is any change occurring at the n-th iteration, it must be the negative cycle that causes it.
2. Floyd-Warshall
What if I want to solve for all pairs’ shortest paths? We can apply Bellman-Ford to every node, which would give me the shortest path, which would be N²M. There’s a more efficient way of doing it with DP.
Let’s take a look at the following example.
What is the shortest path from 1 to 2?
What is the shortest path from 1 to 3?
Recurrence: We can think of either an arbitrary node k is added or not to calculate the shortest paths for every pair. And we can do that for every node.
Let
Then we have two cases to consider:
(1) k is not included in the shortest path:
(2) k is included in the shortest path:
So the final recurrence relation looks like this:
Pseudocode of Floyd Warshall:
Running time: O(N³)
Space: O(N²)
Can we apply DP to find the longest paths?
Yes, but we need to be careful that it doesn’t involve a cycle, and we get a simple path in a graph.
As seen in the graph below, if there is a cycle, the longest path will be infinitely increase.
As long as it doesn’t have a cycle, we can modify Djikstra’s, Bellman-Ford’s, Floyd-Warshall’s to calculate the longest paths.
But when it comes to DAG, we know for sure that it doesn’t have a cycle. So for a DAG, we can use topological sorting to calculate the longest paths which would take O(N+M).
We can also use Djikstra’s to calculate the shortest distance of DAG by negating the distances but its running time is O(M log N), which is longer than O(M+N), so it’s more efficient to use topological ordering.
If there is a cycle, we can apply Traveling Salesman Problem (TSP)’s dynamic programming method. TSP is to figure out, given a complete graph with edge weight indicating a cost, what is the path to visit every vertex minimizing the cost.
By focusing on the last hop from k to j (from the diagram above), the path P’ visited every vertex in set S up to k exactly once and it is the shortest path.
Recurrence has the set of the nodes that should be visited and what node I am currently visiting. Starting at the source node, every node is visited with j, which is the last stop of each tour and i indicates the second to last city to stop.
For each node, every subset from the starting point to that node is explored so that the minimum distance from the starting node to every other node in the subset is calculated.
So far we have seen how dynamic programming can be applied to calculate the shortest paths in graphs. If you have any questions or feedback, please leave a comment.
