最短路問題
圖論問題：在于抽象，怎么建圖！
資料結構中對于稀疏圖的定義為：有很少條邊或弧（邊的條數|E|遠小于|V|2）的圖稱為稀疏圖（sparse graph），反之邊的條數|E|接近|V|2，稱為稠密圖（dense graph），此定義來自百度百科，實際上是一種樸素的理解，簡單來說邊越多，圖就越稠密
一、單源最短路
1.所有邊權為證數
（1）Dijkstra演算法（樸素）
Dijkstra演算法
基本思想: 設定頂點集合S并不斷地作貪心選擇來擴充這個集合，一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知，
步驟:
- 初始時，S中為空，設u是G的某一個頂點（從起點開始），把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用陣列dist記錄當前每個頂點所對應的最短特殊路徑長度，
- 每次從V-S中取出具有最短特殊路徑長度的頂點u，將u添加到S中，同時對陣列dist作必要的修改，
- 一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度，
【Dijkstra演算法迭代程序】
【題目描述】
給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值，
請你求出 11 號點到 nn 號點的最短距離，如果無法從 11 號點走到 nn 號點，則輸出 ?1?1，
輸入格式
第一行包含整數 nn 和 mm，
接下來 mm 行每行包含三個整數 x,y,zx,y,z，表示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz，
輸出格式
輸出一個整數，表示 11 號點到 nn 號點的最短距離，
如果路徑不存在，則輸出 ?1?1，
資料范圍
1≤n≤500,
1≤m≤105,
圖中涉及邊長均不超過10000，輸入樣例：
3 3 1 2 2 2 3 1 1 3 4輸出樣例：
3
思路：
-
初始化距離——dist陣列
dist[0] = 0,dist[i] = +無窮 -
回圈迭代程序：
n次（源點也計算），S{ }集合：記錄所有當前已經確定最短距離的點！t<—— 找到不在S中的，且距離最近的點（跳板）t加入S- 用
t來更新其它點的距離
重邊：去最短邊即可
自環：無影響
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N]; //稠密圖一般使用鄰接矩陣
int dist[N]; //記錄每個節點距離起點的最短距離距離
bool st[N]; //true表示已經確定最短路 屬于s集合
int dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 初始化起點到各個點的距離
dist[1] = 0; // 源點到源點的距離為0
// 迭代回圈n次, 每次可以確定一個點到源點的最短路（t點），然后更新其它點的距離
for(int i = 0; i < n; i ++)
{
int t = -1; // 用于找到第一個點，便于更新第一個點
for (int j = 1; j <= n; j ++ ) // 遍歷dist陣列——找到沒有確定最短路徑的節點中距離源點最近的點t（找到跳板）
if(!st[j] && (t == -1 || dist[t] > dist[j])) // 不在S中的，且距離最近的點
t = j;
st[t] = true; // 加入s集合
// 找到了距離最小的點t，并用最小的點t去更新其他的點到起點的距離
for (int j = 1; j <= n; j ++ ) // 更新其它點的距離（最短距離）
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); // 如有重邊：取最短邊
}
int t = dijkstra();
printf("%d", t);
return 0;
}
for(int i=0;i<n;i++) { t=-1 } 這里為什么t要賦值為 -1?
回答: 由于每一次都要找到還沒有確定最短路距離的所有點中，距離當前的點最短的點，t = - 1是為了在st這個集合中找第一個點方便更新（比較得出最短）所設定的，
（2）堆優化版Dijkstra演算法
思路：
堆優化版的dijkstra是對樸素版dijkstra進行了優化，在樸素版dijkstra中時間復雜度最高的尋找距離最短的點O(n^2)可以使用最小堆優化，
- 一號點的距離初始化為零，其他點初始化成無窮大，
- 將一號點放入堆中，
- 不斷回圈，直到堆空，每一次回圈中執行的操作為：
彈出堆頂（與樸素版diijkstra找到S外距離最短的點相同，并標記該點的最短路徑已經確定），
用該點更新臨界點的距離，若更新成功就加入到堆中，
時間復雜度分析
尋找路徑最短的點：O(n)
加入集合S：O(n)
更新距離：O(mlogn)
【acwing 850. Dijkstra求最短路 II】
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為非負值，
請你求出 1 號點到 n 號點的最短距離，如果無法從 1 號點走到 n 號點，則輸出 ?1，
輸入格式
第一行包含整數 nn 和 mm，
接下來 m 行每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z，
輸出格式
輸出一個整數，表示 1 號點到 n 號點的最短距離，
如果路徑不存在，則輸出 ?1，
資料范圍
1≤n,m≤1.5×105,
圖中涉及邊長均不小于 0，且不超過 10000，輸入樣例：
3 3 1 2 2 2 3 1 1 3 4輸出樣例：
3
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
//first:該節點到起點的距離 second:節點編號
typedef pair<int, int> PII;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];//存放點到源點的距離
bool st[N];
int n, m;
void add(int a, int b, int c) // 添加一條邊a->b，邊權為c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra()
{
//1.
memset(dist, 0x3f, sizeof dist);//初始化距離
priority_queue<PII, vector<PII>, greater<PII> > heap;//用堆來維護最短距離
//小根堆的定義方式,PII的第一個變數存盤的是距離,第二個變數存盤的是該點的編號,內部按照第一個變數排序,即按距離排序
dist[1] = 0;
heap.push({0, 1});// 1號點已知道距離，加進來
//2.
while(heap.size())
{
//拿到不在集合中 且距離最近的點t （拿到跳板t）
auto t=heap.top();//選擇最小的距離的點
heap.pop();//利用完該點之后要彈出
int ver = t.second, distance = t.first;// ver表示該點的編號
if(st[ver]) continue;// 如果被訪問過了(冗余備份)，跳過
st[ver] = true;
/*
堆優化版的是將距離直接加入到堆中.
例如:dist[5]=9(在堆中{9,5},第一次更新時加入),dist[5]=7(在堆中{7，5},第二次更新時加入)
使用時用的是dist[5]=7,將該點({7,5})彈出后,在下一次回圈中,如果{9,5}在堆頂的話,使用時
兩者間肯定要選距離要小的那個,不能使用{9,5}重復更新,所以要用st陣列進行標記
*/
for(int i = h[ver]; i != -1; i =ne[i])
{
int j = e[i];
if(dist[j] > dist[ver] + w[i])//如果j到起點的距離大于ver到1的距離加上ver到j的距離，就更新值的大小
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j}); // 最新的跳板t加入堆
/*
更新距離之后將該點的距離加入到堆中,這也是上述為何要進行標記的原因,
因為一個點的距離加入堆的次數可能有兩次甚至更多,這樣會影響到其他的點
例如:
{9,5},{7,5},{10,6},如果{7,5}被彈出后,堆中剩余的是{9,5},{10,6},堆頂
的元素是{9,5}而5這個點的距離已經被使用過了,所以要將{9,5}這個點忽視掉
*/
}
}
}
if(dist[n] == INF) return -1;
else return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = dijkstra();
cout << t;
return 0;
}
2.存在負權邊
（1）Bellman-Ford
Bellman - ford 演算法是求含負權圖的單源最短路徑的一種演算法，效率較低，代碼難度較小，其原理為連續進行松弛，在每次松弛時把每條邊都更新一下，若在 n-1 次松弛后還能更新，則說明圖中有負環，因此無法得出結果，否則就完成，
松弛操作：
思路：
for n 次
{
備份資料，防止串聯
for 所有邊 a ---> b (w)
{
//更新（松弛操作）
dist[b] = min(dist[b], backup[a] + w);
}
}
限定k條邊的原因：可能出現負權環
為什么要用backip[N]備份資料？
為什么是dist[n]>0x3f3f3f3f/2， 而不是dist[n]==0x3f3f3f3f
5號節點距離起點的距離是無窮大，利用5號節點更新n號節點距離起點的距離，將得到109?2，109?2, 雖然小于10^9, 但并不存在最短路，(在邊數限制在k條的條件下)，
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數，
請你求出從 1 號點到 n 號點的最多經過 kk 條邊的最短距離，如果無法從 1 號點走到 nn 號點，輸出
impossible，注意：圖中可能 存在負權回路 ，
輸入格式
第一行包含三個整數 n,m,k，
接下來 mm 行，每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z，
輸出格式
輸出一個整數，表示從 1 號點到 n 號點的最多經過 k 條邊的最短距離，
如果不存在滿足條件的路徑，則輸出
impossible，資料范圍
1≤n,k≤500,
1≤m≤10000,
任意邊長的絕對值不超過10000，輸入樣例：
3 3 1 1 2 1 2 3 1 1 3 3輸出樣例：
3
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e5 + 10;
int dist[N];//dist[i]表示節點1到節點i的最短距離
int back[N];//備份陣列防止串聯
int n, m, k;//k代表最短路徑最多包涵k條邊
struct Edge
{
int a, b, w;
}edges[M];//結構體存邊
int bellman_ford()
{
//初始化距離陣列
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//1.迭代k次（不超過k條邊）
for(int i = 0; i < k; i ++)
{
memcpy(backup, dist, sizeof dist);// 備份
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], backup[a] + w);//每次用備份的距離（上一次）更新新距離，避免發生串聯
}
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i ++ )
{
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
int t = bellman_ford();
if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else cout << dist[n];
return 0;
}
（2）SPFA
\[SPFA 演算法是 Bellman-Ford演算法 的佇列優化演算法的別稱，通常用于求含負權邊的單源最短路徑，以及判負權環，SPFA一般情況復雜度是O(m) 最壞情況下復雜度和樸素 Bellman-Ford 相同，為O(nm)， \]Bellman_ford演算法會遍歷所有的邊，但是有很多的邊遍歷了其實沒有什么意義，我們只用遍歷那些到源點距離變小的點所連接的邊即可，只有當一個點的前驅結點更新了，該節點才會得到更新；因此考慮到這一點，我們將創建一個佇列每一次加入距離被更新的結點，
dist[b] = min(dist[b], dist[a] + w)只有當dist[a]小了，dist[b]才會變小，因此每次迭代操作佇列里邊存盤的是所有變小的a(節點)，用它來更新后面與它相連的所有點（更新它的所有后繼），這些點可以理解為【待更新其它點的點】，（用更新過的點去更新其它點，只有我變小了，我后面的人也才會跟著變小！）
思路：
st[N]; // 判斷某點是否被使用過
1. queue <--- 1
2.while(佇列不空)
{
//2.1
t <--- q.front();
q.pop();
//2.2列舉t的所有出邊 更新t的所有出邊 t ---> b (w)
{
更新
判重，新點加入佇列 queue <--- b
}
}
3.隊空 結束
st陣列的作用：判斷當前的點是否已經加入到佇列當中了；已經加入佇列的結點就不需要反復的把該點加入到佇列中了，就算此次還是會更新到源點的距離，那只用更新一下數值而不用加入到佇列當中，
即便不使用st陣列最終也沒有什么關系，但是使用的好處在于可以提升效率，
【spfa求最短路】
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數，
請你求出 1 號點到 n 號點的最短距離，如果無法從 1 號點走到 n 號點，則輸出
impossible，資料保證不存在負權回路，
輸入格式
第一行包含整數 n 和 m，
接下來 m 行每行包含三個整數x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z，
輸出格式
輸出一個整數，表示 1 號點到 n 號點的最短距離，
如果路徑不存在，則輸出
impossible，資料范圍
1≤n,m≤105,
圖中涉及邊長絕對值均不超過10000，輸入樣例：
3 3 1 2 5 2 3 -3 1 3 4輸出樣例：
2
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];//存放點到源點的距離
bool st[N];
int n, m;
void add(int a, int b, int c) // 添加一條邊a->b，邊權為c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;//取出佇列后 標記為已用過
//用t去去更新所有出邊（后繼）
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];
if(!st[j])//如果j節點尚未加入佇列（判重）
{
q.push(j);
st[j] = true;//待更新其它點的點入隊 標記
}
}
}
}
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if(t == INF) puts("impossible");
else cout << t;
return 0;
}
【spfa判斷負環】
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數，
請你判斷圖中是否存在負權回路，
輸入格式
第一行包含整數 n 和 m，
接下來 m 行每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z，
輸出格式
如果圖中存在負權回路，則輸出
Yes，否則輸出No，資料范圍
1≤n≤2000,
1≤m≤10000,
圖中涉及邊長絕對值均不超過 10000，輸入樣例：
3 3 1 2 -1 2 3 4 3 1 -4輸出樣例：
Yes
思路：
維護一個計數cnt[]陣列，當cnt[x]>=n時，則表明出現負環！
1、
dist[x]記錄虛擬源點到x的最短距離2、
cnt[x]記錄當前x點到虛擬源點最短路的邊數，初始每個點到虛擬源點的距離為0，只要他能再走n步，即cnt[x] >= n，則表示該圖中一定存在負環，由于從虛擬源點到x至少經過n條邊時，則說明圖中至少有n + 1個點，表示一定有點是重復使用3、若
dist[j] > dist[t] + w[i],則表示從t點走到j點能夠讓權值變少，因此進行對該點j進行更新，并且對應cnt[j] = cnt[t] + 1,往前走一步
【注意】：該題是判斷是否存在負環，并非判斷是否存在從1開始的負環，因此需要將所有的點都加入佇列中，更新周圍的點
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];//存放點到源點的距離
int cnt[N];//cnt[x] 表示 當前從1-x的最短路的邊數
bool st[N];
int n, m;
void add(int a, int b, int c) // 添加一條邊a->b，邊權為c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa()
{
// 這里不需要初始化dist陣列為 正無窮/初始化的原因是， 如果存在負環， 那么dist不管初始化為多少， 都會被更新
queue<int> q;
//不僅僅是1了， 因為點1可能到不了有負環的點， 因此把所有點都加入佇列
for(int i = 1; i <= n; i ++)
{
q.push(i);
st[i] = true;
}
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;//取出佇列后 標記為已用過
//用t去去更新所有出邊（后繼）
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;//維護cnt陣列
if(cnt[j] >= n) return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}
二、多源最短路
Floyd
思想：動態規劃
時間復雜度：O（n * n * n）
演算法核心代碼模板：
void floyd()
{
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
給定一個 n 個點 m 條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數，
再給定 k 個詢問，每個詢問包含兩個整數 x 和 y，表示查詢從點 x 到點 y 的最短距離，如果路徑不存在，則輸出
impossible，資料保證圖中不存在負權回路，
輸入格式
第一行包含三個整數 n,m,k，
接下來 m 行，每行包含三個整數 x,y,z，表示存在一條從點 x 到點 y 的有向邊，邊長為 z，
接下來 k 行，每行包含兩個整數 x,y，表示詢問點 x 到點 y 的最短距離，
輸出格式
共 k 行，每行輸出一個整數，表示詢問的結果，若詢問兩點間不存在路徑，則輸出
impossible，資料范圍
1≤n≤200,
1≤k≤n2
1≤m≤20000,
圖中涉及邊長絕對值均不超過 10000，輸入樣例：
3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3輸出樣例：
impossible 1
【參考代碼】
-
f[i, j, k]表示從i走到j的路徑上除i和j點外只經過1到k的點的所有路徑的最短距離，那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]，
因此在計算第k層的f[i, j]的時候必須先將第k - 1層的所有狀態計算出來，所以需要把k放在最外層， -
讀入鄰接矩陣，將次通過動態規劃裝換成從i到j的最短距離矩陣
-
在下面代碼中，判斷從
a到b是否是無窮大距離時，需要進行if(t > INF/2)判斷，而并非是if(t == INF)判斷，原因是INF是一個確定的值，并非真正的無窮大，會隨著其他數值而受到影響，t大于某個與INF相同數量級的數即可
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int dist[N][N]; // 存盤 x 到 y 的最短距離
int n, m, Q;
void floyd()
{
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main()
{
cin >> n >> m >> Q;
// 初始化
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if(i == j) dist[i][j] = 0;
else dist[i][j] = INF;
// 讀入
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = min(dist[a][b], c); // 避免了重邊和自環，只會保存最小的距離
}
floyd();
// 查詢
while(Q --)
{
int a, b;
cin >> a >> b;
int t = dist[a][b];
if(t > INF / 2) puts("impossible");
else cout << t << endl;
}
return 0;
}
三、總結
在理解思路的基礎上，學習總結代碼！
學習內容源自：
acwing演算法基礎課
注：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412985.html
標籤：其他
下一篇：異或的用法