任意兩點間的最短路問題 Floyd-Warshall演算法-有解無憂

這一演算法與之前的Bellman-F=Ford演算法一樣，都可以判斷負環

只需要檢查dp [i] [j] 是負數的頂點i即可

 1 // 求解任意兩點間的最短路徑問題
 2 // Floyed-Warshall演算法
 3 // 復雜度O(N^3),N為頂點數
 4 
 5 #include <cstdio>
 6 #include <iostream>
 7 
 8 using namespace std;
 9 // 用dp的思路來求解
10 // dp[k][i][j]:從i到j，只利用前K個節點的最短路
11 // dp[k][i][j]=dp[k-1][i][k] + dp[k-1][k][j]
12 // 由于后一層所需的，都來自前一層，而前一層所需
13 // 然后在考慮回圈順序，定k，并且維護最小，所以中間元素必定使用之前維護的在k行k列的元素
14 // 而維護最小值時，k行k列元素，在回圈中，加和一定大于原來的值（否則存在d[i][j]<0,存在負圈)
15 // 所以維護最小值時不更新，依舊是上一串列中的值
16 // 所以dp陣列可以降維進行運算
17 
18 const int max_N = 200+2;
19 const int max_E = 10000+2;
20 const int INF = 1e9;
21 
22 int dp[max_N][max_N];
23 int N,E;
24 
25 void floyd_warshall()
26 {
27     for(int k=0;k<N;++k)
28     {
29         for(int i=0;i<N;++i)
30         {
31             for(int j=0;j<N;++j)
32             {
33                 dp[i][j]=min( dp[i][j],dp[i][k]+dp[k][j] );
34             }
35         }
36     }
37 }
38 
39 int main()
40 {
41     scanf("%d %d",&N,&E);
42     int a,b,c;
43     for(int i=0;i<N;++i)
44     {
45         for(int j=0;j<N;++j)
46         {
47             if(i==j)
48             {
49                 dp[i][j]=0;
50             }
51             else
52             {
53                 dp[i][j]=INF;
54             }
55         }
56     }
57     for(int i=0;i<E;++i)
58     {
59         scanf("%d %d %d",&a,&b,&c);
60         dp[a][b]=c;
61         // 無向圖
62         dp[b][a]=c;
63     }
64     floyd_warshall();
65 
66     for(int i=0;i<N;++i)
67     {
68         for(int j=0;j<N;++j)
69         {
70             printf("%d ",dp[i][j]);
71         }
72         printf("\n");
73     }
74     return 0;
75 }
76 /*
77 7 10
78 0 1 2
79 0 2 5
80 1 2 4
81 1 3 6
82 1 4 10
83 2 3 2
84 3 5 1
85 4 5 3
86 4 6 5
87 5 6 9
88 
89 
90 
91 
92 0 2 5 7 11 8 16
93 2 0 4 6 10 7 15
94 5 4 0 2 6 3 11
95 7 6 2 0 4 1 9
96 11 10 6 4 0 3 5
97 8 7 3 1 3 0 8
98 16 15 11 9 5 8 0
99 */

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88253.html

標籤：其他

上一篇：https服務關于埠的使用問題

下一篇：DHCP動態主機配置求查缺補漏