Bellman-Ford¶

Mathematical Background¶

Let \(G = (V, E)\) be a directed graph with edge weights \(w(e)\). For each vertex \(v \in V\), the algorithm maintains a distance estimate \(d[v]\), initialized to \(\infty\) except for the source vertex \(s\) where \(d[s] = 0\).

The algorithm performs relaxation on all edges \(|V| - 1\) times. For each edge \((u, v) \in E\), the relaxation step is:

If after \(|V| - 1\) iterations, a shorter path is still found, the graph contains a negative cycle.

Algorithm Steps¶

1. Initialize distances from the source to all vertices as infinity, except the source itself (distance 0).

2. Repeat |V| - 1 times: a. For each edge (u, v) in the graph:

   1. If d[v] > d[u] + weight(u, v), update d[v].

3. Check for negative cycles by iterating through all edges again. If any distance can be updated, a negative cycle exists.

Implementation¶

Below is a Python implementation of the Bellman-Ford algorithm:

 1def bellman_ford(graph, source):
 2    # Initialize distance from source node
 3    distance = {node: float('infinity') for node in graph}
 4    distance[source] = 0
 5
 6    # Relax all edges |V| - 1 times
 7    for _ in range(len(graph) - 1):
 8        for u in graph:
 9            for v, w in graph[u].items():
10                # Update distance if shorter path found
11                if distance[u] + w < distance[v]:
12                    distance[v] = distance[u] + w
13
14    # Check for negative cycles
15    for u in graph:
16        for v, w in graph[u].items():
17            if distance[u] + w < distance[v]:
18                raise ValueError("Graph contains a negative cycle")
19
20    return distance

Key Properties¶

• Time Complexity: O(|V| * |E|)

• Space Complexity: O(|V|)

• Correctness: Guaranteed to find shortest paths if no negative cycles exist.

• Use Cases: Network routing, currency arbitrage detection, and systems with negative weights.

Label Correcting Approach¶

Bellman-Ford is considered a "label correcting" algorithm, as it iteratively updates distance labels until no further improvements are possible. This contrasts with "label setting" algorithms like Dijkstra's, which permanently fix distances once they are determined.

Problem Statement¶

We have a directed weighted graph \(G\). The weights of the edges in \(G\) can also be negative. We know that graph \(G\) contains no cycles with negative total weight.

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

# This is a code example, comments remain in Finglish
def bellman_ford(graph, start):
    distance = {node: float('infinity') for node in graph}
    distance[start] = 0

Bellman-Ford Algorithm¶

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

We know that the length of the shortest walk between two vertices in graph \(G\) is equal to the length of the shortest path. This is because if the shortest walk contains a repeated vertex, it implies the existence of a cycle with a positive length (according to the problem's assumption, cycles cannot have negative lengths). This cycle can be removed to obtain a shorter walk, which is a contradiction.

For the base cases of this DP table, we have \(dp_{i, sc} = 0\) and \(dp_{0, u \neq sc} = \infty\). To compute \(dp_{i, j}\), we consider all incoming edges to \(j\). For each edge \(e\) from \(u_e\) to \(j\) with weight \(w_e\), we calculate the value \(dp_{i-1, u_e} + w_e\). The minimum of these values gives the solution for \(dp_{i, j}\). Thus:

To find the length of the shortest path from vertex \(sc\) to vertex \(u\), the value \(dp_{n-1, u}\) suffices. This is because a path from \(sc\) to any other vertex can have at most \(n\) vertices and \(n-1\) edges. Based on 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 one.

Order Analysis¶

To update all cells of \(dp_i\) for each vertex, we perform operations proportional to its in-degree. We know that the sum of in-degrees of all vertices equals \(|E(G)|\) (edge count). Therefore in total, we've performed \(\mathcal{O}\left(|V(G)|.|E(G)|\right)\) operations. The memory order used is also \(\mathcal{O}\left(|V(G)|^2\right)\) .

Memory Order Optimization¶

To optimize the amount of memory used, the first dimension can be removed. As a result, the memory complexity becomes \(\mathcal{O}\left(|V(G)|\right)\).

Then, for each edge, \(|V(E)| - 1\) steps are performed to update the dp value of the destination vertex of the edge. By "updating", we mean 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 operation keep the dp entries at their desired values? The answer is yes.

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

Now, if we check after the \(n-1\)-th step, we find that \(dp_u = dp_{n-1, u}^{\prime}\). Therefore, after the \(n-1\)-th step, the dp entries have the desired values.

Finding the Shortest Path¶

After all this discussion, a question arises: if we want the optimal path itself from \(sc\) to another vertex like \(des\), what should we do?

To solve this question, we need to slightly modify the previous algorithm. We consider an auxiliary array called \(par\) with \(|V(G)|\) elements. Initially, we set all elements of \(par\) to -1. Now, when we consider an edge \(e\) and \(dp_{v_e} > dp_{u_e} + w_e\) holds, we set \(par_{v_e}\) to \(u_e\).

\(par_u\) effectively represents the previous vertex in the optimal path from \(sc\) to \(u\). To obtain the path from \(sc\) to \(des\), we maintain a variable \(nw\) and until \(nw \neq sc\), we set \(nw\) to \(par_{nw}\) and prepend \(nw\) to the current obtained path.

To prove that we will definitely reach the vertex \(sc\) and that the obtained path is optimal, we assume an array \(lst\). \(lst_u\) equals the number of the last stage in which \(dp_u\) was changed. We know \(lst_u > lst_{par_u}\) holds. (Proof is left to the reader) Therefore, every time we set \(nw\) to \(par_{nw}\), \(lst_{nw}\) decreases, so we do not loop and will definitely reach \(sc\).

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

Negative Cycle¶

You might wonder, if it's not guaranteed whether the graph has a negative cycle or not, how can we determine if a negative cycle exists? (Assuming we have optimized memory usage).

First, suppose instead of \(|V(G)| - 1\) iterations, we run the algorithm for \(|V(G)|\) iterations. We call an iteration of the algorithm "good" if the value of at least one cell in the \(dp\) array changes. We know that if iteration \(i\) is not good, then subsequent iterations will also not be good. (If no values change, subsequent iterations will behave exactly like iteration \(i\), and no cells will change).

Now, if there is no negative cycle, based on previous reasoning, iteration \(|V(G)|\) will definitely not be good. (All cells will have reached their final values in the previous iteration and will not change). However, if a negative cycle exists, we know the \(dp\) values of its vertices will never stabilize. The negative cycle itself can be traversed multiple times, causing the \(dp\) values of the cycle's vertices to approach \(-\infty\). We also know that if an iteration is not good, then all values have stabilized. From these arguments, it follows that if a negative cycle exists, all iterations will be good.

Thus, we conclude: If there is no negative cycle, iteration \(|V(G)|\) will not be good, and if a negative cycle exists, iteration \(|V(G)|\) will definitely be good. Therefore, to check for the existence of a negative cycle, it suffices to check whether iteration \(|V(G)|\) is good.

To find the negative cycle itself, similar to the case without negative cycles, maintain an auxiliary array called \(par\). Starting from a vertex whose value changed in iteration \(|V(G)|\), trace back the optimal path from \(sc\) — the negative cycle will necessarily lie along this path. (This part can be proven based on the reasoning in this section).