In the previous task, we say a DP formulation for the shortest path problem with positive edge weights \(w\) from a given source node \(s\):
and for \(v \neq s\)
The state graph is the same as the input graph and so this formulation will work if and only if the input graph is acyclic.
So what can we do if the input graph contains cycles, is it still possible to solve it with dynamic programming? YES. But we need to change the formulation so that the resulting state graph is acyclic.
Doing so requires some imagination and is problem dependent. However there are some general tricks.
Suppose that you have a formulation with states \(s \in S\). Imagine that you add a parameter \(i\) to the formulation and manage to make sure that each state \((s, i)\) only depends on states \((s, j)\) with \(j < i\). Then your new state graph is clearly acyclic since any path on it
must has have a strictly increasing \(i\) coordinates
This might seem a bit abstract so let's see a concrete example with the shortest path problem.
Define a new state \((v, i)\) with the following subproblem definition:
\(dp(v, i)\) equals the length of the shortest path from \(s\) to \(v\) that traverses at most \(i\) edges.
How to the subproblems relate to each other? To reach node \(i\) using at most \(i\) edges, we have two possibilities:
- We reach some neighbor \(u\) of \(v\) using at most \(i - 1\) edges and then traverse edge \((u, v)\)
- We reach \(v\) using at most \(i - 1\) edges.
Mathematically, this means that
The base case is when \(i = 0\). In this case we only use paths with \(0\) edges the only node that is reachable from the source \(s\) is itself. If \(d(v, i)\) is not defined, that is, the path of at most \(i\) edges from \(s\) to \(v\) exists, we define \(d(v, i) = \infty\). In particular, it means that we initialize \(d(v, 0) = \infty\) for each \(v \neq s\).
With this formulation we can now solve the following problem:
Given a weighted graph \(G\) and a source \(s\), what is the shortest path from \(s\) to \(v\) using at most \(i\) edges?
Notice that with positive edge weights, any shortest path uses at most \(|V| - 1\) edges (such a shortest path cannot have cycles). This means that we only need to compute the answer for states until \(i = |V| - 1\). The answer to the shortest path problem from \(s\) to \(v\) will therefore be \(dp(v, |V| - 1)\).
What did we lose by extending the space state? We lost efficiency, now there are \(O(|V|^2)\) states.
It should be easy now to implement this ideas. Simply create a matrix to store the values of \(dp(v, i)\) and compute them in increasing order of \(i\) using the above relation.
Since for each \(i = 0, \ldots, |V| - 1\) we need to iterate over the graph, the total runtime will be \(O(|V| (|V| + |E|))\). This is equal to \(O(|V| |E|)\) for any connected graph.