Shortest paths, revisited
Recall that we were interested in solving the shortest path problem, where we are given a digraph $G$ with edge weights, a source vertex $s$ and a destination vertex $t$. We saw how to solve this using a greedy approach. Now, we are ready to revisit a problem that we were introduced to earlier that we couldn't solve: how to find the shortest path in a graph that contains negative edge weights.
One of the things some of you observed was that if there's a negative cycle (i.e. a cycle for which the sum of its edge weights is negative) on a path from $s$ to $t$, then there's no shortest path from $s$ to $t$. The proof is not complicated: if there's a negative cycle, then we can take the negative cycle as much as we like to decrease the cost of the path by an arbitrary amount.
Now, we will consider a non-greedy approach (read: dynamic programming) to solving the problem that will allow us to use negative edge weighs. Our algorithm will even be able to determine whether any of our paths contain a negative cycle, so we can figure out whether there a shortest path exists.
Rather than computing the shortest path from a source $s$ to every other node, we will consider sort of the backwards version of the problem, where we compute the shortest path from every vertex to our destination $t$.
The single-destination shortest paths problem is: Given a directed graph $G = (V,E)$ with an edge weight function $e: E \to \mathbb R$ and a destination vertex $t$, find a shortest path from $v$ to $t$ for every $v \in V$.
Note that there's no technical reason for doing this—we can just as well define and solve the single-source shortest paths problem using this approach, but KT does it this way to use with another problem we won't be talking about. A nice exercise would be to reformulate the following results in the context of single-source shortest paths.
Because we plan to use dynamic programming, we need to determine what subproblem is appropriate to compute in the service of finding a shortest path. Here, we can take some inspiration from our greedy approach: recall that Dijkstra's algorithm kept an estimated weight of the path from the source $s$ to each vertex $v$.
There are a few similar subproblems that we can try:
- weight of a shortest path from $v$ to $t$ that uses only the first $i$ vertices (assuming you've given your vertices some arbitrary order),
- weight of a shortest path from $v$ to $t$ that uses exactly $i$ edges,
- weight of a shortest path from $v$ to $t$ that uses at most $i$ edges,
To help clarify this decision, here is a useful result that we won't prove but is similar to something you may have seen in discrete math.
Suppose $G$ has no negative cycles. Then there is a shortest path from $u$ to $v$ that does not repeat any vertices.
One consequence of this result is that any shortest path will have at most $n-1$ edges in it, since any path that has more edges will revisit some vertex.
We will define $OPT(i,v)$ to be the weight of a shortest path from $v$ to $t$ that uses at most $i$ edges. So if we want to compute the shortest path from $s$ to $t$, we would want to compute $OPT(n-1,s)$.
Let's consider this informally first. Let's consider a shortest path from a vertex $v$ to our destination $t$, which would have weight $OPT(i,v)$. How can we decompose this path? Since we want to express this in terms of some shorter path, it makes sense to consider the first edge in our path, say $(v,x)$, followed by the shortest path from that vertex $x$ to $t$. So we have the following possibilities.
- Our shortest path from $v$ to $t$ uses fewer than $i$ edges. In this case, our work is done: we just use the shortest path we already have, so we must have $OPT(i,v) = OPT(i-1,v)$.
Our shortest path from $v$ to $t$ uses exactly $i$ edges. In this case, we want to express the weight of our path as a path with fewer edges, but we also know the cost of at least one edge: the one leaving $v$. So we must have $OPT(i,v) = w(v,x) + OPT(i-1,x)$ for some vertex $x$.
However, unlike the problems we saw before, this isn't just a matter of considering whether some edge is or isn't in the path—we have possibly many neighbours to choose from.
Luckily, there is an obvious choice: choose the one that gives us a path of minimal weight. This is expressed as
\[OPT(i,v) = \min_{(v,x) \in E} \{w(v,x) + OPT(i-1,x)\}.\]
We then put this together to get the following.
Let $OPT(i,v)$ be the weight of a shortest path $\mathcal P_{i',v}$ from $v$ to $t$ that has at most $i$ edges. Then $OPT(i,v)$ satisfies the recurrence
- If $i = 0$ and $v = t$, then $OPT(i,v) = 0$,
- If $i = 0$ and $v \neq t$, then $OPT(i,v) = \infty$,
- If $i \gt 0$, then
\[OPT(i,v) = \min\left\{ OPT(i-1, v), \min_{(v,x) \in E} \{OPT(i-1,x) + w(v,x)\}\right\}.\]
We will prove this by induction on $i$. Our base case is $i = 0$. In this case if $v = t$, then we can reach $t$ from $v$ (itself) with 0 edges, so $OPT(i,v) = 0$. However, if $v \neq t$, then $t$ is not reachable from $v$, so $OPT(i,v) = \infty$.
Now consider $i \gt 0$. We assume that $OPT(i',v')$ is the weight of a shortest path from $v'$ to $t$ that uses at most $i'$ edges for all $i' \lt i$. Let $\mathcal P_{i,v}$ be a shortest path from $v$ to $t$ that uses at most $i$ edges.
First, we argue that
\[OPT(i,v) \geq \min\left\{ OPT(i-1, v), \min_{(v,x) \in E} \{OPT(i-1,x) + w(v,x)\}\right\}.\]
There are two cases.
- If $\mathcal P_{i,v}$ contains fewer than $i$ edges, then it is a possible solution for the shortest path from $v$ to $t$ with at most $i-1$ edges. Therefore, $OPT(i,v) \geq OPT(i-1,v)$.
- Suppose $\mathcal P_{i,v}$ contains exactly $i$ edges. Let $x$ be the vertex following $v$ and consider the path from $x$ to $t$ in $\mathcal P_{i,v}$. The weight of this portion of the path is $OPT(i,v) - w(v,x)$. But this is a possible solution for the shortest path from $x$ to $t$ on $i-1$ edges, so we have
\begin{align*}
OPT(i,v) - w(v,x) &\geq OPT(i-1,x) \\
OPT(i,v) &\geq OPT(i-1,x) + w(v,x)
\end{align*}
We note additionally that since $\mathcal P_{i,v}$ has minimal weight, $OPT(i-1,x) + w(v,x)$ must be minimal among all choices of neighbours of $v$, so
\[OPT(i,v) \geq \min_{(v,x) \in E} OPT(i-1,x) + w(v,x).\]
Next, we show that
\[OPT(i,v) \leq \min\left\{ OPT(i-1, v), \min_{(v,x) \in E} \{OPT(i-1,x) + w(v,x)\}\right\}.\]
- Consider $\mathcal P_{i-1,v}$, the shortest path from $v$ to $t$ with at most $i-1$ edges. This path is a shortest path from $v$ to $t$ with at most $i-1$ edges. Therefore, $OPT(i,v) \leq OPT(i-1,v)$.
- Next, consider a neighbour of $v$, say $x$, and consider the path $\mathcal P_{i-1,x}$, which is the least weight path from $x$ to $t$ with at most $i-1$ edges. The cost of this path is $OPT(i-1,x)$. Then we can create a path from $v$ to $t$ via $x$ by adding the edge $(v,x)$ to $\mathcal P_{i-1,x}$. This is a path from $v$ to $t$ with at most $i$ edges, since we added one edge, and the cost of this path is $OPT(i-1,x) + w(x,v)$. Since this is a possible solution for a shortest path from $v$ to $t$ with at most $i$ edges, we have
\[OPT(i,v) \leq OPT(i-1,x) + w(v,x)$.\]
Furthermore, since the choice of $x$ among neighbours of $v$ was arbitrary, we must have that
\[OPT(i,v) \leq \min_{(v,x) \in E} OPT(i-1,x) + w(v,x)$.\]
Therefore by the two inequalities above, we have
\[OPT(i,v) = \min\left\{ OPT(i-1, v), \min_{(v,x) \in E} \{OPT(i-1,x) + w(v,x)\}\right\}.\]
As usual, the recurrence leads us to a straightforward algorithm that fills out a table.
\begin{algorithmic}
\PROCEDURE{shortest-paths}{$G,t$}
\FORALL{$v \in V$}
\STATE $P[0,v] \gets \infty$
\ENDFOR
\STATE $P[0,t] \gets 0$
\FOR{$i$ from $1$ to $n-1$}
\FORALL{$v \in V$}
\STATE $P[i,v] \gets P[i-1,v]$
\FORALL{$(v,x) \in E$}
\STATE $P[i,v] \gets \min\{P[i,v], P[i-1,x]+w(v,x)\}$
\ENDFOR
\ENDFOR
\ENDFOR
\ENDPROCEDURE
\end{algorithmic}
This algorithm is pretty straightforward. The tricky part is counting the number of iterations this algorithm makes. Just like with Dijkstra's algorithm, it's easy to conclude that there must be something like $O(mn^2)$ just by looking at the definition of the loops, but if we observe how the edges are chosen, we see that only edges the leave a particular vertex are examined at each iteration, so every edge is examined at most once. So the inner two loops together comprise a total of $O(m)$ iterations. In total, this gives us $O(mn)$ time.
On the other hand, the algorithm clearly requires $O(n^2)$ space. This seems like a lot, especially compared to Dikjstra's algorithm. It turns out that we can do better by applying some of the same ideas.