文章目錄
-
- 概述
- Dijkstra算法
- Bellman-Ford算法和SPFA算法
- Floyd算法
概述
\qquad 本文把求圖的最短路徑的幾種方法綜合闡述，已經列舉出相應的練習題，以求透徹了解和熟練解決最短路徑相關的問題。最短路徑，就是求一條從起點到終點的路徑，使得這條路徑上所有邊的邊權之和最小。這三種方法分别是Dijkstra算法，Bellman-Frod算法和SPFA算法以及Floyd算法。
Dijkstra算法
這個算法适合解決：單源最短路勁問題。（即給定圖G和起點s,通過算法得到s到達其他每個定點的最短距離。）
算法的基本思想：對圖G(V,E)設定集合S,存放已被通路的頂點，然後每次從集合V-S中選擇與起點s的最短距離最小的一個頂點（記為u），通路并加入集合S.之後，令頂點u為中介點，優化起點s與所有從u能到達的頂點v之間的最短距離。這樣的操作執行n次（n為頂點個數），直到集合S已包含所有頂點。
注意：該算法隻适合所有邊權都是非負數的情況，如果出現負數，那麼該算法将會出錯，最好使用SPFA算法。
關于這個算法的過程，算法筆記給了一個有趣的例子，大家可以先看一下。
好了，看完了例子，接下來是思考如何編碼了。個人覺得編碼就是寫出資料結構使輸入輸出的資訊以及中間處理時産生的可用的資訊得以儲存，并盡可能簡單。為什麼要儲存，因為我們寫代碼，其實就是操縱的這些資訊。那麼對于這道題，首先，它是圖，是以有鄰接矩陣表示和鄰接表表示兩種情況。這兩個任選一個，就可以表達出圖了，之後就可以對其進行操作了。另外，本題還需要維護一個數組和變量。比如說是結點s到各個頂點的距離最大值數組，各個結點是否被通路數組（這個數組就實作了上面說的那個存放已通路元素的集合S以及未通路元素的集合V-S）等，這裡如果一開始沒法思考全，可以先寫思考到的，等到編碼的時候遇到了，再繼續添加。等熟練了，大多數都是套路，就那麼幾個變量。
那麼，這裡圖是全部代碼的一個核心資料結構，圍繞着它展開。他有鄰接表和鄰接矩陣兩種表達。鄰接矩陣時，它的時間複雜度在 O ( V 2 ) O(V^2) O(V2).鄰接表時，它的複雜度在 O ( V 2 + E ) O(V^2+E) O(V2+E).
這是最短距離，那路徑怎麼求，其實還是加一個數組記錄資訊，無一例外，需要新的資訊，就需要考慮增加新的資料結構或者是利用原來的資料結構，他們就是用來存儲資訊的。在這裡，我們考慮到加入新的一個結點時，如果最短距離變小，那麼該點的前驅就設定成u,意思就是說從u到v目前最短。就可以啦。
可是真實的考題，一般還會比這個稍微複雜一點，（就是說需要多定義幾個數組的事！）一般呢，有三種變體：新增邊權（比如說花費），新增點權（比如說每個城市能收集到的物資），直接問有多少條最短路徑。下面來一一舉例：
1.新增邊權。
這是一個典型的最短路徑的問題，并且求的隻是最短距離。但是人家加了一個邊權，就是題目中的風暴時間。好了，本題求的是單源最短路徑，邊權都是非負數，适合Dijkstra算法。
後來我覺得這道題是動态的邊權。AC的代碼：
#include <iostream>
using namespace std;
const int MAXV = 1000; //本題的頂點數為500，還不算大。
const int INF = 1000000000; //設INF是一個很大的數。
int g[MAXV][MAXV]; //圖
bool vit[MAXV] = { false }; //記錄是否通路
int d[MAXV]; //記錄最短距離
struct node {
int qi1;
int end1;
};
node g1[MAXV][MAXV]; //記錄風暴資訊，看，就是加個數組的事。
void Dijkstra(int s,int n) {
d[s] = 0;
vit[s] = true;
for (int i = 1; i < n; i++) {
int u = -1; int MIN = INF;
for (int j = 1; j < n; j++) {
if(vit[j]==false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if (u == -1) { return; }
vit[u] = true;
for (int v = 1; v < n; v++) {
if (vit[v]==false&&g[u][v]!=0) {
//在這裡需要單獨更新一下邊的權值，因為這裡疊加了風暴的因素，是以是動态的權值。
if ((d[u] >= g1[u][v].qi1 - g[u][v]) && (d[u] <= g1[u][v].end1)) { g[u][v] = g1[u][v].end1 - d[u] + g[u][v]; }
else {}
if (d[u] + g[u][v] < d[v]) {
d[v] = d[u] + g[u][v];
}
}
}
}
}
int main() {
int N, M;
cin >> N >> M;
fill(d, d + MAXV, INF); //先置為最大值
for (int i = 0; i < M; i++) {
int a, b, c, d1, e;
cin >> a >> b >> c >> d1 >> e;
g[a][b] = g[b][a] = c;
g1[a][b].qi1 = d1;
g1[b][a].qi1 = d1;
g1[a][b].end1 = e;
g1[b][a].end1 = e;
//這個地方是先把與1相連的邊，先給初始化。
if (a == 1) {
if (d1 > c) { d[b] = c;}
else { d[b] = e+c; }
}
if (b == 1) {
if (d1 > c) { d[a] = c; }
else { d[a] = e+c; } //權值就是它風暴結束的那一天+渡河需要的時間。
}
}
Dijkstra(1,N+1);
cout << d[N]+1;
return 0;
}
//輸出最短路徑
void DFS(int s,int n) { //s為起點，n為目标點
if (n == s) { //這是遞歸出口。
cout << s<<endl;
return;
}
DFS(s, pre[n]); //這個pre數組是在更新最短距離時更新的。
cout << n << endl;
/*
1.要把遞歸出口寫在最前面。
2.要把在這一層的輸出放在往後的層的輸出的下面，因為下面的深層應該是先輸出的。
這是關于遞歸的幾點了解。
*/
}
更多的變種可參考這篇文章。
另一個相似變種 Dijkstra+DFS
Bellman-Ford算法和SPFA算法
\qquad Dijkstra算法可以很好的解決無負權值的圖的最短路徑問題，但如果出現了負權值，Dijkstra算法就會失效。為了解決這一問題，需要使用Bellman-Ford算法（簡稱BF算法）。該算法不僅可以處理單源最短路徑問題，而且對于權值的正負沒有要求。該算法隻有一個要求，即沒有從源點可達的負權值回路（回路的權值和為負）。
Floyd算法
\qquad 這個算法可以用來解決全源最短路徑問題。即對給定圖G(V,E),求任意兩點u,v之間的最短路徑的長度，時間複雜度是 O ( n 3 ) O(n^3) O(n3).Floyd算法基于這樣一個事實：如果存在頂點k,使得以k為中介點時頂點i和頂點j的目前最短距離縮短，則使用頂點k作為頂點i和頂點j的中介點。
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXV = 200;
const int INF = 1000000;
int n, m;
int dis[MAXV][MAXV]; //dis數組表示最短距離，dis[i][j]表示頂點i和頂點j的最短距離。
void Floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
}
int main() {
int u, v, w;
fill(dis[0], dis[0] + MAXV * MAXV, INF); //dis數組賦初值。
cin >> n >> m; //頂點數和邊數
for (int i = 0; i < n; ++i) {
dis[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
cin >> u >> v >> w; //頂點和邊權值
dis[u][v] = dis[v][u] = w;
}
Floyd();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << dis[i][j]<<" ";
}
cout << endl;
}
return 0;
}
這是圖的最短路徑問題的全部内容了。