Bellman-Ford
One observation we can make is that in the end, we really don't care how many edges a shortest path actually uses. In that sense, all we really need to do is keep track of the minimum weight of the path from each vertex. So instead of keeping track of a table of size $O(n^2)$, we can keep track of an array $d$ of estimated weights of shortest paths.
The problem with this is that this may not be enough information to reconstruct the actual path itself. We take a similar approach to Dijkstra's algorithm and keep track of the successors for each vertex as we update the estimated weights $d$. In doing so, we reduce our space requirements from a table of size $O(n^2)$ to two arrays of size $n$, which is $O(n)$.
This leads to the following algorithm attributed to Bellman, who we saw earlier as the inventor of dynamic programming, and Ford, who we will see again very shortly when we get into network flows. But even though the algorithm is called Bellman-Ford, they didn't publish together: Ford published the algorithm in 1956, while Bellman published it in 1958. Even this isn't the only instance: Moore also published the algorithm in 1957 and sometimes also gets attribution, while Shimbel published it in 1955 and does not.
\begin{algorithmic}
\PROCEDURE{bellman-ford}{$G,t$}
\FORALL{$v \in V$}
\STATE $d[v] \gets \infty$
\ENDFOR
\STATE $d[t] \gets 0$
\FOR{$i$ from $1$ to $n-1$}
\FORALL{$v \in V$}
\STATE $d[v] \gets \min\{d[v],\min\limits_{(v,x) \in E} d[x] + w(v,x)\}$
\ENDFOR
\ENDFOR
\ENDPROCEDURE
\end{algorithmic}
The running time of this algorithm is still $O(mn)$ by the same argument as before and the space requirements have clearly changed to $O(n)$. What is not as obvious is that $d$ ends up holding the weights of the shortest paths for each vertex. And in order to correctly recover the path, we would need to correctly store the successor for each vertex, though we ignore that here. So we will simply argue that Bellman-Ford correctly computes the weight of the shortest path.
After the $i$th iteration of the outer loop of Bellman-Ford, the following properties hold for every vertex $v \in V$:
- If $d[v] \neq \infty$, then $d[v]$ is the weight of some path from $v$ to $t$,
- If there is a path from $v$ to $t$ with at most $i$ edges, then $d[v]$ is the length of the shortest path from $v$ to $t$ with at most $i$ edges.
We will prove this by induction on $i$. First, we consider $i = 0$. We have $d[t] = 0$ and $d[v] = \infty$ for all $v \neq t$, since there are no paths from $v$ to $t$ with 0 edges.
Now consider $i \gt 0$ and consider an update to $d[v] = d[x] + w(v,x)$. By our inductive hypothesis, $d[x]$ is the weight of a path from $x$ to $t$, so $d[x] + w(v,x)$ is the weight of a path from $v$ to $t$. So (1) holds.
Now, consider a shortest path $P$ from $v$ to $t$ with at most $i$ edges. Let $x$ be the first vertex after $v$ in $P$. Then the subpath $P'$ from $x$ to $t$ is a path from $x$ to $t$ with at most $i-1$ edges.
By our inductive hypothesis, $d[x]$ is the weight of a shortest path from $x$ to $t$ with at most $i-1$ edges after $i-1$ iterations of the outer loop of Bellman-Ford. So $d[x] \leq w(P')$.
Then on the next iteration, we consider the edge $(v,x)$. We have
\[d[v] \leq d[x] + w(v,x) \leq w(P') + w(v,x) = w(P).\]
So after $i$ iterations, $d[v]$ is at most the weight of the shortest path from $v$ to $t$ with at most $i$ edges. So (2) holds.
To complete our algorithm, we would need to show how to store successors and that the path that we get from following those successors from $s$ gets us the shortest $v,t$ path. Unlike with Dijkstra's algorithm, we would need to show that it's not possible to create a cycle through our computation. One can show that if our graph does not have any negative cycles, then we will not end up with a cycle in the successor subgraph, and from there show that the paths that are obtained via the successor graph are actually the shortest paths from $v$ to $t$.
Network flow
We will now examine a class of problems related to the idea of network flow. This seems a bit specific compared to the broader techniques that we've been looking at, but the interesting thing about all of these problems is that we can't actually solve them using any of our prior techniques. Rather, they operate under a principle of starting with a simple and not necessarily optimal solution, and iteratively refine and improve that solution until it is optimal.
All of the problems we'll see are based on the idea of flow through a graph.
A flow network is a tuple $G = (V,E,s,t,c)$, where $(V,E)$ is a digraph with a source $s \in v$ and a sink $t \in V$ and every edge $e \in E$ has a capacity $c(e) \geq 0$.
To simplify things, we make the following assumptions.
- No edges enter the source $s$.
- No edges exit the sink $t$.
- Capacities are integers (i.e. $c:E \to \mathbb N$).
- Every vertex $v \in V$ is reachable from the source $s$.
Here, we have a flow network with edges labelled with their capacities.
Intuitively, we want to consider the flow of some material through our graph from $s$ to $t$. Here, material is abstract, but can represent things like traffic or liquid. Let's formally define what flow is.
An $s,t$-flow is a function $f:E \to \mathbb N$ that satisfies
- capacity: for all edges $e \in E$, $0 \leq f(e) \leq c(e)$;
- conservation: for all vertices $v \in V - \{s,t\}$,
\[\sum\limits_{e = (u,v) \in E} f(e) = \sum\limits_{e = (v,w) \in E} f(e).\]
In other words, the flow going into a vertex must be the same as the flow leaving the vertex.
We say that the value of a flow $f$ is
\[v(f) = \sum\limits_{e = (s,v) \in E} f(e).\]
Here, we have our network from above, with flow applied as labelled.
One thing to note here is that this is clearly not the most "stuff" that we can put through this network. This leads us to our problem.
The maximum flow problem is: Given a flow network $G = (V,E,s,t,c)$, find a flow $f$ of maximum value.
A seemingly natural approach for this is to use a greedy algorithm: just look at the edges with the largest capacities and measure the flow travelling on those edges. Then if we have any leftover flow, we can redirect it appropriately across the rest of the network.
Here, we have our working example after applying a "greedy" strategy of finding the largest path to saturate our flow.
We first send 8 flow through path 1 and the remaining 2 through path 2. We then try to send as much as we can through path 3. This results in a flow of 16.
However, the following is a better flow.
The main problem with this approach is the same one that fails for a lot of attempts via greedy algorithms: sometimes the greedy choice isn't the best choice and we have to go back and make some change.