?負循環：循環的環的循環總和為負的情況。（如圖情況）

思路：1.將從源點到其他各點的最短路設為無窮大， 源點處的距離為0；

? ? ? ? ?? 2.利用Bellman-Ford求到各個點的最短路，需要循環n-1次（有n個頂點）

原因：如果假設該圖沒有負環存在，則最短經過每個點一次（即n-1條邊），因此最多循環n-1次

? ? ? ? ? ? ? ? ? ? ? ?? 設圖中的某兩個點u 和v ，G[u, v]? =? dist; 如果 d[u] > d[v] + dist; 則需要更新當前節點的距離。

? ? ? ? ?? 3.如果存在負環，則在進行第n次循環時，d的值任何會更新，如果出現這樣的情況，此時可以判斷該圖中存在負環

?

Bellman-Ford算法：

//從0開始 struct edge{int u, v, w; };edge es[maxn]; int d[maxn]; int V, E;void Bellman_Frod(int s){for(int i = 0; i < V; i++) d[i] = INF;d[s] = 0;while(1){bool Update = false;for(int i = 0; i < E; i++){edge e = es[i];if(d[e.u] != INF&&d[v] > d[u] + e.w){d[e.v] = d[e.u] + e.w;Update = true;}}if(!Update) break;} }

判斷負圈

struct Node{int u, v, w; };edge es; int d[maxn];int V, E; //頂點個數V，邊個數E void isCycleBellman_Ford(int s){//初始化距離 for(int i = 0; i < V; i++) d[i] = INF;d[s] = 0;/* *** 2*放松所有的邊V-1次*從源點到各點的最短路*/for(int i = 1; i < V; i++){for(int j = 0; j < E; j++){edge e = es[j];if(d[e.u] != INF&&d[e.v] > d[e.u] + e.w)d[e.v] = d[e.u] + e.w;}} /**** 3*如果d的值更新則為負環 */for(int i = 0; i < E; i++){edge e = es[j];if(d[e.u] != INF&&d[e.u] > d[e.v] + e.w)return true;}return false; }

?

1(0) --------------->(1)/|\ || || | -1| |-1| || \|/(3)<----------------(2)

如這樣一個圖：可以肯定的是任何節點與其自身的距離始終為0，如果當我們從第0點遍歷都第0點時，結果確是-2，顯然這樣的結果是不正確的。而這樣的環一定是負環。因此我們只需判斷任意點到自身的距離是否存在負數的情況即可。

int d[maxn][maxn]; int maze[maxn][maxn];int V, E; //頂點個數V，邊個數E /*以有向圖為例*/ void init(){for(int i = 0; i < V; i++){for(int j = 0; j < V; j++){if(i == j) d[i][j] = 0;else d[i][j] = INF; }}for(int i = 0; i < E; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);d[u][v] = w;} } bool iscycleFloyd(){init();for(int k = 0; k < V; k++){//逐個選擇所有的頂點作為源點for(int i = 0; i < V; i++){//選擇所有頂點作為目標for(int j = 0; j < V; j++){if(d[i][k] + d[k][j] < d[i][j]){d[i][j] = d[i][k] + d[k][j];}}} }//判斷負環for(int i = 0; i < V; i++)if(d[i][i] < 0) return true;return false; }

?

?

總結

以上是生活随笔為你收集整理的检查是否有负循环（Bellman Ford， Floyd-Warshall）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。