Bellman-Ford¶

Problem Statement¶

We are given a weighted directed graph \(G\). The weights of \(G\)'s edges can also be negative. We know that graph \(G\) does not contain a cycle with a negative total weight.

Now, for each vertex, we want to find the length of the shortest path from vertex \(sc\) to all other vertices. The length of a path is the sum of its edge weights.

Bellman-Ford Algorithm¶

To solve this problem, we first define a \(dp\) table of dimensions \(|V(G)| \times |V(G)|\), where \(dp_{i,j}\) is the length of the shortest walk from vertex \(sc\) to vertex \(j\) using at most \(i\) edges.

We know that the length of the shortest walk between two vertices in graph \(G\) is also equal to the length of the shortest path, because if the shortest walk contains two repeated vertices, it implies a cycle whose length is positive (as per the problem statement, a cycle cannot have a negative length). This cycle can therefore be removed, leading to a walk with a shorter length, which is a contradiction.

For the base cases of this DP, we know that \(dp_{i, sc} = 0\) and \(dp_{0, u \neq sc} = \infty\). Now, to find \(dp_{i, j}\), we consider all edges entering \(j\). If for each edge \(e\) that enters \(j\) from \(u_e\) with weight \(w_e\), we calculate \(dp_{i-1, u_e} + w_e\), the minimum of these values becomes the answer for \(dp_{i, j}\). Consequently:

To obtain the length of the shortest path from vertex \(sc\) to vertex \(u\), having the value \(dp_{n-1, u}\) is sufficient. This is because a path from vertex \(sc\) to another vertex has at most \(n\) vertices and \(n-1\) edges, and according to the DP definition and the fact that the shortest walk between two vertices in \(G\) is necessarily a path, this value is exactly the required value.

Complexity Analysis¶

To update all entries of \(dp_i\), we perform operations proportional to the in-degree for each vertex. We know that the sum of in-degrees of all vertices equals \(|E(G)|\). Thus, in total, we perform \(\mathcal{O}\left(|V(G)|.|E(G)|\right)\) operations. The space complexity used is \(\mathcal{O}\left(|V(G)|^2\right)\).

Memory Optimization¶

To optimize the memory usage, the first dimension can be removed. Consequently, the memory complexity becomes \(\mathcal{O}\left(|V(G)|\right)\).

Then, for \(|V(G)| - 1\) stages, for each edge, the \(dp\) value of the edge's head vertex is updated. Updating means that if edge \(e\) goes from vertex \(u_e\) to \(v_e\) with weight \(w_e\), we set \(dp_{v_e} = \min(dp_{v_e}, dp_{u_e} + w_e)\).

Now a question arises: does performing this preserve the desired values in the \(dp\) table? The answer is yes.

If we consider the DP from the previous section as \(dp^{\prime}\), after the \(i\)-th stage of updating \(dp\), we know that \(dp_u\) is equal to one of \(dp_{i, u}^{\prime}, dp_{i+1, u}^{\prime}, \dots, dp_{n-1, u}^{\prime}\). (Proof of this lemma is left to the reader.)

Now, if we check after the \((n-1)\)-th stage, we find that \(dp_u = dp_{n-1, u}^{\prime}\). Consequently, after the \((n-1)\)-th stage, the values in the \(dp\) table are the desired ones.

Finding the Shortest Path¶

After all this discussion, a question might come to your mind: what if we need the optimal path itself from \(sc\) to another vertex like \(des\)?

To answer this question, we need to slightly modify the previous algorithm. We introduce an auxiliary array of size \(|V(G)|\) named \(par\). Initially, we set all entries of \(par\) to -1. Now, if when considering edge \(e\), we have \(dp_{v_e} > dp_{u_e} + w_e\), we set \(par_{v_e}\) to \(u_e\).

\(par_u\) is effectively the previous vertex on the optimal path from \(sc\) to \(u\). To find the path from \(sc\) to \(des\), we maintain a variable \(nw\) and, as long as \(nw \neq sc\), we set \(nw\) to \(par_{nw}\) and prepend \(nw\) to the current path.

To prove that we necessarily reach vertex \(sc\) and that the path obtained is an optimal path, we assume an array \(lst\). \(lst_u\) is the number of the last stage where \(dp_u\) was updated. We know that \(lst_u > lst_{par_u}\). (Proof is left to the reader.) Thus, each time we set \(nw\) to \(par_{nw}\), \(lst_{nw}\) decreases, so we do not enter a cycle and will definitely reach \(sc\).

The length of the path will also be \(dp_{des}\) because if we add an edge with weight \(w\) to the path at each step, the value of \(dp_{nw}\) decreases exactly by \(w\). Since \(dp_{sc} = 0\), the length of the path will be exactly \(dp_{des}\).

Negative Cycle¶

You might wonder, if it's not guaranteed whether the graph has a negative cycle or not, how do we detect one (in the case where memory has been optimized)?

First, assume we run \(|V(G)|\) stages instead of \(|V(G)| - 1\) stages. We call a stage of the algorithm "good" if at least one of the \(dp\) values changes. We know that if the \(i\)-th stage is not good, then subsequent stages will also not be good. (If no value changes, then subsequent stages will behave exactly like the \(i\)-th stage, and no value will change.)

Now, if we do not have a negative cycle, then according to previous arguments, the \(|V(G)|\)-th stage must not be good. (All values would have reached their final amounts in the previous stage and will not change). Now, if a negative cycle exists, we know that the \(dp\) values of its vertices will never stabilize. The negative cycle itself can be traversed multiple times, which causes the \(dp\) values of the cycle's vertices to approach \(-\infty\). We know that if a stage is not good, then all values have stabilized. Based on these statements, it follows that if we have a negative cycle, all stages will be good.

So, we know that if we don't have a negative cycle, the \(|V(G)|\)-th stage is not good, and if we do have a negative cycle, the \(|V(G)|\)-th stage must be good. Therefore, to check for the presence of a negative cycle, it is sufficient to check if the \(|V(G)|\)-th stage is good.

To find the negative cycle itself (similar to the case without negative cycles), take an auxiliary array named \(par\). Trace back from a vertex whose \(dp\) value changed in the \(|V(G)|\)-th stage; the negative cycle will necessarily be present in this path. (This section's reasoning can be used to prove this.)