文章目錄
- 一、前言
- 二、Bellman-Ford算法
- 三、Bellman-Ford算法隊列優化SPFA 算法
- 最後
一、前言
單源最短路，指的是求一個點，到其他所有點的最短距離。
即起點是固定的，單一的
注意：最短路問題的核心在于，把問題抽象成一個最短路問題，并建圖。圖論相關的問題，不側重于算法原理，而側重于對問題的抽象。
上篇文章
【圖論——第四講】dijkstra算法求單源最短路及其堆優化提到
所有邊的權重都是正數，通常有兩種算法
1.樸素Dijkstra
時間複雜度O(n2)，其中n是圖中點的個數，m是邊的個數
2.堆優化版的Dijkstra
時間複雜度O(mlogn)，其中n是圖中點的個數，m是邊的個數
如果圖存在負邊權呢？還能用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詳細步驟分析
- 初始dist[1] = 0
- 找到了未辨別且離源點1最近的結點1，标記1号點，用1号點更新其他所有點的距離，2号點被更新成dist[2] = 2，3号點被更新成dist[3] = 5
- 找到了未辨別且離源點1最近的結點2，辨別2号點，用2号點更新其他所有點的距離，4号點被更新成dist[4] = 4
- 找到了未辨別且離源點1最近的結點4，辨別4号點，用4号點更新其他所有點的距離，5号點被更新成dist[5] = 5
- 找到了未辨別且離源點1最近的結點3，辨別3号點，用3号點更新其他所有點的距離，4号點被更新成dist[4] = 3
-
結束
得到1号點到5号點的最短距離是5，對應的路徑是1 -> 2 -> 4 -> 5，并不是真正的最短距離
那麼存在負邊權的圖怎麼求最短距離呢？
二、Bellman-Ford算法
時間複雜度 O(nm), n 表示點數，m 表示邊數
Bellman - ford 算法是求
含負權圖
的單源最短路徑的一種算法，效率較低，代碼難度較小。其原理為連續進行松弛，在每次松弛時把每條邊都更新一下，若在 n-1 次松弛後還能更新，則說明圖中有負環，是以無法得出結果，否則就完成。
bellman - ford算法的具體步驟
for n次
for 所有邊 a,b,w (松弛操作)
dist[b] = min(dist[b],dist[a] + w)
int n, m; // n表示點數，m表示邊數
int dist[N]; // dist[x]存儲1到x的最短路距離
struct Edge // 邊，a表示出點，b表示入點，w表示邊的權重
{
int a;
int b;
int w;
}edges[M];
// 求1到n的最短路距離，如果無法從1走到n，則傳回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次疊代仍然會松弛三角不等式，就說明存在一條長度是n+1的最短路徑，
//由抽屜原理，路徑中至少存在兩個相同的點，說明圖中存在負權回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b],dist[a] + w)
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
/*
是否能到達n号點的判斷中需要進行if(dist[n] > ox3f3f3f3f/2)判斷，
而并非是if(dist[n] == 0x3f3f3f3f)判斷，原因是0x3f3f3f3f是一個
确定的值，并非真正的無窮大，會随着其他數值而受到影響，dist[n]大于
某個與0x3f3f3f3f相同數量級的數即可
*/ 三、Bellman-Ford算法隊列優化SPFA 算法
SPFA 算法是 Bellman-Ford算法 的隊列優化算法的别稱，通常用于求含負權邊的單源最短路徑，以及判負權環。
SPFA一般情況複雜度是O(m) 最壞情況下複雜度和樸素 Bellman-Ford 相同，為O(nm)。n 表示點數，m 表示邊數
算法思想
Bellman_ford算法會周遊所有的邊，但是有很多的邊周遊了其實沒有什麼意義，我們隻用周遊那些到源點距離變小的點所連接配接的邊即可，隻有當一個點的前驅結點更新了，該節點才會得到更新；是以考慮到這一點，我們将建立一個隊列每一次加入距離被更新的結點。考慮用BFS來做優化。用一個隊列queue，來存放距離變小的節點。
算法步驟
queue <– 1
while queue 不為空
(1) t <– 隊頭
queue.pop()
(2)用 t 更新所有出邊 t –> b，權值為w
queue <– b (若該點被更新過，則拿該點更新其他點)
模闆如下：
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。
請你求出 1 号點到 n 号點的最短距離，如果無法從 1 号點走到 n 号點，則輸出 impossible。
資料保證不存在負權回路。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],ne[N],e[N],w[N],idx;
int m,n;
queue<int>q;
int st[N],d[N]; //st表示隊列裡是否有某值;
// 存儲每個點到1号點的最短距離
// 存儲每個點是否在隊列中
void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
d[1]=0;
q.push(1);
st[1]=1; //表示隊列裡有1了;
while(q.size())
{
int t=q.front();q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]>d[t]+w[i]) //是否可更新;
{
d[j]=d[t]+w[i]; //更新;
if(!st[j]) //判斷隊列裡是否已經有j;
{
st[j]=1;
q.push(j); //沒有則将j插入隊列;
}
}
}
}
if(d[n]>0x3f3f3f3f/2)cout<<"impossible"; //可能存在負權邊;
else cout<<d[n];
}
int main()
{
memset(h,-1,sizeof(h));
memset(d,0x3f,sizeof(d));
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
spfa();
} 若要使用SPFA算法，
一定要求圖中不能有負權回路。
隻要圖中沒有負權回路，都可以用SPFA，這個算法的限制是比較小的。
當然我們也可以用PSFA算法來判斷圖中有沒有負環。
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。
如果圖中存在負權回路，則輸出 Yes，否則輸出 No。
請你判斷圖中是否存在負權回路。
int n; // 總點數
int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲所有邊
int dist[N], cnt[N]; // dist[x]存儲1号點到x的最短距離，cnt[x]存儲1到x的最短路中經過的點數
bool st[N]; // 存儲每個點是否在隊列中
// 如果存在負環，則傳回true，否則傳回false。
bool spfa()
{
// 不需要初始化dist數組
// 原理：如果某條最短路徑上有n個點（除了自己），那麼加上自己之後一共有n+1個點，由抽屜原理一定有兩個點相同，是以存在環。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果從1号點到x的最短路中包含至少n個點（不包括自己），則說明存在環
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
} 最後
莫言真理無窮盡，寸進自有寸進歡