題目 有邊數限制的最短路

給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你求出從 1 號點到 n號點的最多經過 k條邊的最短距離，如果無法從 1號點走到 n號點，輸出 impossible。

注意：圖中可能 存在負權回路 。

輸入格式
第一行包含三個整數 n,m,k。

接下來 m行，每行包含三個整數 x,y,z，表示存在一條從點 x到點 y的有向邊，邊長為 z。

點的編號為 1～n。

輸出格式
輸出一個整數，表示從 1號點到 n號點的最多經過 k條邊的最短距離。

如果不存在滿足條件的路徑，則輸出 impossible。

數據范圍
1 ≤ n,k ≤ 500,
1 ≤ m ≤ 10000,
1 ≤ x,y ≤ n，
任意邊長的絕對值不超過 10000。

輸入樣例：
3 3 1
1 2 1
2 3 1
1 3 3
輸出樣例：
3

算法分析

1、問題：為什么Dijkstra不能使用在含負權的圖中？

（這是以前錯誤的分析，若看完這個例子分析覺得正確的說明對最短路理解得還不夠透徹，這里不做刪除）

分析：如圖所示：
若通過Dijkstra算法可以求出從1號點到達4號點所需的步數為3 (每次選擇離源點最短距離的點更新其他點)
但實際上從 1 號點到達 4 號點所需步數為 1 (1 –> 2 –> 3),因此不能使用 Dijkstra 解決含負權圖的問題

正確的分析
Dijkstra算法的3個步驟

1. 找到當前未標識的且離源點最近的點t
2. 對t號點點進行標識
3. 用t號點更新其他點的距離
   反例
   

結果：

dijkstra算法在圖中走出來的最短路徑是1 -> 2 -> 4 -> 5，算出 1 號點到 5 號點的最短距離是2 + 2 + 1 = 5，然而還存在一條路徑是1 -> 3 -> 4 -> 5，該路徑的長度是5 + (-2) + 1 = 4，因此 dijkstra 算法失效

dijkstra詳細步驟

1. 初始dist[1] = 0
2. 找到了未標識且離源點1最近的結點1，標記1號點，用1號點更新其他所有點的距離，2號點被更新成dist[2] = 2，3號點被更新成dist[3] = 5
3. 找到了未標識且離源點1最近的結點2，標識2號點，用2號點更新其他所有點的距離，4號點被更新成dist[4] = 4
4. 找到了未標識且離源點1最近的結點4，標識4號點，用4號點更新其他所有點的距離，5號點被更新成dist[5] = 5
5. 找到了未標識且離源點1最近的結點3，標識3號點，用3號點更新其他所有點的距離，4號點被更新成dist[4] = 3
6. 結束
7. 得到1號點到5號點的最短距離是5，對應的路徑是1 -> 2 -> 4 -> 5，并不是真正的最短距離

2、什么是bellman - ford算法？

Bellman - ford 算法是求含負權圖的單源最短路徑的一種算法，效率較低，代碼難度較小。其原理為連續進行松弛，在每次松弛時把每條邊都更新一下，若在 n-1 次松弛后還能更新，則說明圖中有負環，因此無法得出結果，否則就完成。
(通俗的來講就是：假設 1 號點到 n 號點是可達的，每一個點同時向指向的方向出發，更新相鄰的點的最短距離，通過循環 n-1 次操作，若圖中不存在負環，則 1 號點一定會到達 n 號點，若圖中存在負環，則在 n-1 次松弛后一定還會更新)

3、bellman - ford算法的具體步驟

for n次for 所有邊 a,b,w (松弛操作)dist[b] = min(dist[b],back[a] + w)

注意：back[] 數組是上一次迭代后 dist[] 數組的備份，由于是每個點同時向外出發，因此需要對 dist[] 數組進行備份，若不進行備份會因此發生串聯效應，影響到下一個點

4、在下面代碼中，是否能到達n號點的判斷中需要進行if(dist[n] > INF/2)判斷，而并非是if(dist[n] == INF)判斷，原因是INF是一個確定的值，并非真正的無窮大，會隨著其他數值而受到影響，dist[n]大于某個與INF相同數量級的數即可

5、bellman - ford算法擅長解決有邊數限制的最短路問題

時間復雜度 O(nm)
其中n為點數，m為邊數

C ++ 代碼

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510, M = 10010;struct Edge
{int a, b, c;
}edges[M];int n, m, k;
int dist[N];
int last[N];void bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < k; i ++ ){memcpy(last, dist, sizeof dist);for (int j = 0; j < m; j ++ ){auto e = edges[j];dist[e.b] = min(dist[e.b], last[e.a] + e.c);}}
}int main()
{scanf("%d%d%d", &n, &m, &k);for (int i = 0; i < m; i ++ ){int a, b, c;scanf("%d%d%d", &a, &b, &c);edges[i] = {a, b, c};}bellman_ford();if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");else printf("%d\n", dist[n]);return 0;
}

Java 代碼

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class Main {static int N = 510;static int M = 100010;static int n;//總點數static int m;//總邊數static int k;//最多經過k條邊static int[] dist = new int[N];//從1到點到n號點的距離static Node[] list = new Node[M];//結構體static int INF = 0x3f3f3f3f;static int[] back = new int[N];//備份dist數組public static void bellman_ford(){Arrays.fill(dist, INF);dist[1] = 0;for(int i = 0;i < k;i++){back = Arrays.copyOf(dist, n + 1);//由于是從1開始存到nfor(int j = 0;j < m;j++){Node node = list[j];int a = node.a;int b = node.b;int c = node.c;dist[b] = Math.min(dist[b], back[a] + c);}}if(dist[n] > INF/2) System.out.println("impossible");else System.out.println(dist[n]);}public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));String[] str1 = reader.readLine().split(" ");n = Integer.parseInt(str1[0]);m = Integer.parseInt(str1[1]);k = Integer.parseInt(str1[2]);for(int i = 0;i < m;i++){String[] str2 = reader.readLine().split(" ");int a = Integer.parseInt(str2[0]);int b = Integer.parseInt(str2[1]);int c = Integer.parseInt(str2[2]);list[i] = new Node(a,b,c);}bellman_ford();}}
class Node
{int a, b, c;public Node(int a,int b,int c){this.a = a;this.b = b;this.c = c;}
}