The Bellman-Ford algorithm
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph \(G = (V, E)\) with source vertex \(s\) and weight function \(w: E \rightarrow R\), the Bellman-Ford algorithm returns a boolean value indicating wether there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.
The procedure BELLMAN-FORD relaxes edges, progressively decreasing an estimate \(v.d\) on the weight of a shortest path from the source \(s\) to each vertex \(v\in V\) until it achieves the actual shortest-path weight \(\delta(s,v)\). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that reachable from the source.
INITIALIZE-SINGLE-SOURCE(G,s)
for i = 1 to |G.V| - 1
for each edge (u,v) \in G.E
RELAX(u, v, w)
for each edge(u,v) \in G.E
if v.d > u.d + w(u,v)
return FALSE
retturn TRUE
Figure: The execution of the Bellman-Ford algorithm. The source is the vertex \(s\). The \(d\) values appear within the vertices, and blue edges indicate predecessor values: if the edge \((u,v)\) is blue, then \(v.\pi = u\). In this particular example, each pass relaxes the edges in the order \((t,x), (t,y), (t,z), (x,t),(y,x),(y,z),(z,x),(z,s),(s,t),(s,y)\).
(a) The situation just before the first pass over the edges.
(b)-(e) The situation after each successive pass over the edges. Vertices whose shortest-path estimates and predecessors have changed due to a pass are highlighted in orange. The \(d\) and \(\pi\) value in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example.
The figure shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the \(d\) and \(\pi\) values of all vertices in line 2, the algorithm makes \(|V| - 1\) passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2 - 4 and consists of relaxing each edge of the graph once. Figure (b)-(e) shows the state of the algorithm after each of the four passes over the edges. After making |V| - 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We'll see a little later why this check works.)
The Bellman-Ford algorithm runs in \(O(V^2 + VE)\) time when the graph is represented by adjacency lists, since the initialization in line 1 takes \(\Theta(V)\) time, each of the \(|V| - 1\) passes over the edges in lines 2 - 4 takes \(\Theta(V+E)\) time (examining |V| adjacency lists to find the |E| edges), and the for loop of lines 5-7 takes \(O(V + E)\) time. Fewer than \(|V| - 1\) passes over the edges sometimes suffice (see Exercise 22.1-3), which is why we say \(O(v^2 + VE)\) time, rather than \(\Theta(V^2 + VE)\) time. In the frequent case where \(|E| = \Omega(V)\), we can express this running time as \(O(VE)\). Exercise 22.1-5 asks you to make the Bellman-Ford algorithm run in \(O(VE)\) time even when \(|E|= o(V)\).
To prove the correctness of the Bellman-Ford algorithm, we start by showing that if there no negative-weight cycles, the algorithm computes correct shortest-path weights for all vertices reachable from the source.
787. Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
Constraints:
1 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dst
Solution:
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// Initialize the distance array
int[][] dist = new int[n][k + 2]; // 4, 1+2 =3
/**
0 1 2
0 - - -
1 - - -
2 - - -
3 - - -
*/
// 将数组中的每一行都填充为无穷大 (表示初始时所有城市的最小成本未知)
for (int[] row : dist){
Arrays.fill(row, Integer.MAX_VALUE);
}
dist[src][0] = 0; // start: source city // 设置起点城市src在0次中转的成本为0
/**
0 1 2
0 0 0 -
1 - - -
2 - - -
3 - - -
*/
// Iterate over the number of stops from 0 to k + 1
// because allow k stops, so there will be k+ 1 edge
// 从1次中转开始循环, 到(k+1)次中转为止
for (int stops = 1; stops <= k + 1; stops++){
// 在每一轮中转开始时, 将上一轮的成本拷贝到当前轮次
for (int i = 0; i < n; i++){
dist[i][stops] = dist[i][stops - 1];
// dist[0][1] = dist[0][0] = 0
// dist[1][1] = dist[1][0] = -
}
// 遍历所有的航班信息
for (int[] flight : flights){
// [0, 1, 100]
int from = flight[0];//0
int to = flight[1];//1
int price = flight[2]; // 100
if (dist[from][stops - 1] != Integer.MAX_VALUE){
// dist[0][0] = 0
dist[to][stops] = Math.min(dist[to][stops], dist[from][stops - 1] + price);
// dist[1][1] = Math.min(dist[1][1], dist[0][1] + 100);
// dist[1][1] = Math.min(-, 100)
// dist[1][1] = 100
}
}
}
// Find the minimum cost to reach dst with up to k + 1 stops
int minCost = Integer.MAX_VALUE;
for (int stops = 0; stops <= k + 1; stops++){
minCost = Math.min(minCost, dist[dst][stops]);
}
return minCost == Integer.MAX_VALUE ? -1 : minCost;
}
}