最短路徑（Dijkstra、Bellman-Ford和SPFA算法）

• 前言
• 圖的存儲(chǔ)方式
• • 鄰接矩陣
  • 鄰接表
  • • 鏈表建立
    • 利用vector
    • 結(jié)構(gòu)體
• 核心思路
• Dijkstra算法
• • 圖解
  • 基本思想
  • 求解步驟
  • 細(xì)節(jié)解釋
  • • 變量的意義
    • 初始化
    • 迭代次數(shù)
    • 更新條件
  • 完整代碼
• Bellman-Ford算法
• • 思路：
  • 變量說(shuō)明
  • 初始化
  • 完整代碼
• Bellman-Ford 檢測(cè)圖是否含有負(fù)圈（回路）
• • 思路
  • 代碼
• Bellman-Ford 算法優(yōu)化
• SPFA算法
• • 思路
  • 完整代碼
• 算法的比較

前言

提醒一下：最短路徑一般用于有向網(wǎng)（就是有方向和權(quán)值的圖），而最小生成樹一般是用于無(wú)向網(wǎng)。
本來(lái)是想分開寫，不過(guò)想到這樣大家看起來(lái)比較麻煩。就寫在一起了，這樣可以很好的進(jìn)行對(duì)比。

圖的存儲(chǔ)方式

常用的無(wú)非就

鄰接矩陣

鄰接表

鏈?zhǔn)角跋蛐?/li>

鄰接矩陣

這個(gè)可以說(shuō)是最好理解的了，分為以下幾種情況

• 無(wú)權(quán)值得圖，初始化為0，有邊想連（有關(guān)系）就賦值為1
• 有權(quán)值圖（網(wǎng)），初始化為 INF（一個(gè)大的常數(shù)），有邊想連（有關(guān)系）就賦值為 該權(quán)值

鄰接表

可以說(shuō)鄰接表的建圖就很花里胡哨了，如果不理解它的意思，肯定被每一個(gè)人都不一樣的鄰接表給弄糊涂的。為了讓大家看下邊的代碼不亂，特意說(shuō)明一下。

鏈表建立

• 對(duì)于鏈表，就是一個(gè)一維數(shù)組，其中存放表頭節(jié)點(diǎn)，每一個(gè)表頭節(jié)點(diǎn)都連著一個(gè)鏈表，是由其相鄰的頂點(diǎn)組成。

利用vector

基于鏈表中的特性，可以用一個(gè)vector數(shù)組來(lái)代替鏈表

• 如果是不帶權(quán)值的

vector<int>edge[N];int main() {int V, E;cin >> V >> E;for (int i = 0; i < E; ++i){int u,v;cin >> u >> v;edge[u].push_back(v);/*如果是無(wú)向圖edge[u].push_back(v);edge[v].push_back(u);*/}// 遍歷，通過(guò)頂點(diǎn)來(lái)遍歷，for (int i = 1; i <= V; ++i){for (int j = 0; j < edge[i].size(); ++j)cout << edge[i][j] << " ";}}

• 如果有權(quán)值的話，有兩個(gè)地方改就好

#define pi pair<int,int> vector<pi>edge[N];

• 存的時(shí)候，

for (int i = 0; i < E; ++i){int u,v，w;cin >> u >> v>>w;edge[u].push_back(make_pair(v,w));/*如果是無(wú)向圖edge[u].push_back(make_pair(v,w));edge[v].push_back(make_pair(u,w));*/}

結(jié)構(gòu)體

結(jié)構(gòu)體的話就想到與用邊來(lái)作為一個(gè)頭來(lái)建立

//從頂點(diǎn)u到頂點(diǎn)v的權(quán)值為w的邊 struct edge {int u, v, w; }; edge es[N];//儲(chǔ)存所有邊int main() {int V, E;cin >> V >> E;for (int i = 1; i <= E; ++i){int u, v,w;cin >> u >> v>>w;es[i] = edge{ u, v, w };/*如果是無(wú)向圖es[i] = edge{ u, v, w };es[i] = edge{ v, u, w };*/}// 遍歷，通過(guò)邊來(lái)遍歷，for (int i = 1; i <= E; ++i){edge e = es[i];cout << e.u << " " << e.v << " " << e.w << endl;}} 相信說(shuō)到這，就可以慢慢悟了把

核心思路

本來(lái)想放在后頭，不過(guò)怕大家一路看過(guò)去直接迷了。就放在前邊，可以帶著這個(gè)去看.

Dijkstra算法

// dis[k] 中 dis[k] 表示源點(diǎn)到 頂點(diǎn)k的距離(直接到k） //dis[mark] + g[mark][k] 先到當(dāng)前距離短的點(diǎn)mark，通過(guò)這個(gè)點(diǎn)轉(zhuǎn)到k dis[k] = min(dis[k], dis[mark] + g[mark][k]); //取最小的距離

Bellman-Ford和SPFA算法

if (dis[e.v] > dis[e.u] + e.w)dis[e.v] = dis[e.u] + e.w;

其實(shí)大家理解和這兩個(gè)是一個(gè)道理。都可以通過(guò)下面這段話理解。

可以想一下有三個(gè)點(diǎn)，1,2，3.剛開始1到3距離為6,1到2是3,2到3是2.以1為源點(diǎn)，因?yàn)榈巾旤c(diǎn)2的距離小，所以將2加入。這個(gè)時(shí)候在更新距離時(shí)，之前沒有加入2的時(shí)候1到3只有1–>3這個(gè)路徑可以走，而現(xiàn)在2加入后，有新的路徑了1–>2–>3，我們?cè)谒阋幌麻L(zhǎng)度，哇才是5，比直接走到3小，好那么我們就改變路徑。這就是上面代碼的意義。

Dijkstra算法

圖解

由于本博主畫的圖太，借了點(diǎn)圖

----- S是已計(jì)算出最短路徑的頂點(diǎn)的集合
----- U是未計(jì)算出最短路徑的頂點(diǎn)的集合
----- C(3)表示頂點(diǎn)C到起點(diǎn)D的最短距離為3

選擇頂點(diǎn)D
S={D(0)}
U={A(∞), B(∞), C(3), E(4), F(∞), G(∞)}

選取頂點(diǎn)C
S={D(0), C(3)}
U={A(∞), B(13), E(4), F(9), G(∞)}

就這樣當(dāng)作一個(gè)引子

基本思想

把帶權(quán)圖中的所有頂點(diǎn)V分成兩個(gè)集合S和T，S中存放已經(jīng)確定最短路徑的頂點(diǎn)，初始時(shí)，S中僅包含一個(gè)源點(diǎn)； T=V?S,存儲(chǔ)待確定最短路徑的頂點(diǎn)，初始時(shí)，T中包含除源點(diǎn)外的頂點(diǎn)，此時(shí)各頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度為源點(diǎn)到各頂點(diǎn)的弧上的權(quán)值。開始操作時(shí)，從T中選取當(dāng)前最短路徑長(zhǎng)度最小的一個(gè)頂點(diǎn) Vi 加入S，然后修改T中剩余頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度，修改的原是：當(dāng) Vi 的最短路徑長(zhǎng)度與 Vi 到T中的頂點(diǎn)之間的權(quán)值之和小于該頂點(diǎn)的當(dāng)前路徑長(zhǎng)度時(shí)，用前者替換后者。重復(fù)上述過(guò)程，直到S中包含所有的頂點(diǎn)
為止。

簡(jiǎn)單來(lái)說(shuō)，將點(diǎn)分為兩個(gè)集合，將源點(diǎn)放入一個(gè)集合中，其余的點(diǎn)放入另一個(gè)集合。（實(shí)現(xiàn)算法不需要用到集合，可以用一個(gè)bool 數(shù)組來(lái)記錄，為true就表明就加入到了源點(diǎn)所在的集合中）。然后遍歷不在源點(diǎn)集合的點(diǎn)，找到距離源點(diǎn)最近的點(diǎn)。將這個(gè)點(diǎn)加入到源點(diǎn)所在的集合中。然后以這個(gè)點(diǎn)為中轉(zhuǎn)點(diǎn)更新源點(diǎn)到其余點(diǎn)的距離。

求解步驟

將有向網(wǎng)用鄰接矩陣儲(chǔ)存，沒有相連的邊用一個(gè)較大的數(shù)表示。

找到距離源點(diǎn)最近的點(diǎn)，將其加入到源點(diǎn)所在的集合中。

以這個(gè)點(diǎn)為中轉(zhuǎn)點(diǎn)，更新源點(diǎn)到其余點(diǎn)的距離。

細(xì)節(jié)解釋

變量的意義

int g[N][N];//鄰接矩陣存圖，g[i][j] 表示 頂點(diǎn)i帶頂點(diǎn)j的距離 int dis[N];//表示 源點(diǎn)src到 i的最短距離 bool vis[N];//是否在集合中 int stc;//源點(diǎn) int n, m;//n 頂點(diǎn)數(shù)，m邊數(shù)

初始化

void init() {mst(g, 0);mst(vis, 0); //初始化點(diǎn)的集合為空mst(dis, INF);//初始化距離為一個(gè)很大的數(shù) }

迭代次數(shù)

for (int i = 1; i < n; ++i) //n 個(gè)點(diǎn)，只用迭代n-1次就好 要明確算法的結(jié)束標(biāo)識(shí)是：將所有點(diǎn)加入到源點(diǎn)所在的集合，這樣就好理解了。

因?yàn)閯傞_始就將源點(diǎn)放入集合中了，所要就還需要n-1次

更新條件

這就是神秘的松弛操作了 // dis[k] 中 dis[k] 表示源點(diǎn)到 頂點(diǎn)k的距離(直接到k） //dis[mark] + g[mark][k] 先到當(dāng)前距離短的點(diǎn)mark，通過(guò)這個(gè)點(diǎn)轉(zhuǎn)到k dis[k] = min(dis[k], dis[mark] + g[mark][k]); //取最小的距離

可以想一下有三個(gè)點(diǎn)，1,2，3.剛開始1到3距離為6,1到2是3,2到3是2.以1為源點(diǎn)，因?yàn)榈巾旤c(diǎn)2的距離小，所以將2加入。這個(gè)時(shí)候在更新距離時(shí)，之前沒有加入2的時(shí)候1到3只有1–>3這個(gè)路徑可以走，而現(xiàn)在2加入后，有新的路徑了1–>2–>3，我們?cè)谒阋幌麻L(zhǎng)度，哇才是5，比直接走到3小，好那么我們就改變路徑。這就是上面代碼的意義。

完整代碼

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> //#include<unordered_map> #include<ctime> using namespace std; typedef long long ll; #define pi pair<int,int> #define mst(ss,b) memset(ss,b,sizeof(ss)); #define rep(i,k,n) for(int i=k;i<=n;i++) #define INF 0x3f3f3f3f const int N = 2e3 + 10;int g[N][N];//鄰接矩陣存圖，g[i][j] 表示 頂點(diǎn)i帶頂點(diǎn)j的距離 int dis[N];//表示 源點(diǎn)src到 i的最短距離 bool vis[N];//是否在集合中 int stc;//源點(diǎn) int n, m;//n 頂點(diǎn)數(shù)，m邊數(shù) void init() {mst(g, 0);mst(vis, 0); //初始化點(diǎn)的集合為空mst(dis, INF);//初始化距離為一個(gè)很大的數(shù) }void Dijkstra() {dis[stc] = 0;//自己到自己的距離肯定為1vis[stc] = 1;//把源點(diǎn)存入集合中for (int i = 1; i < n; ++i) //n 個(gè)點(diǎn)，只用迭代n-1次就好{int mark = stc, midis = INF;int j;for ( j = 0; j < n; ++j){if (!vis[j] && dis[j] < midis)//從沒有加入的點(diǎn)中{//尋找一個(gè)最小值mark = j;midis = dis[j];}}// mark 就是找到的 不在集合內(nèi)部且當(dāng)前路徑長(zhǎng)度（與源點(diǎn)的距離）最小的頂點(diǎn)if (mark != stc) //如果不是本身vis[mark] = 1; //將點(diǎn)j加入集合//對(duì)不在集合中的頂點(diǎn)修改dis[j]的值for (int k = 0; k < n; ++k){if (!vis[k])// dis[k] 中 dis[k] 表示源點(diǎn)到 頂點(diǎn)k的距離(直接到k）//dis[mark] + g[mark][k] 先到當(dāng)前距離短的點(diǎn)mark，通過(guò)這個(gè)點(diǎn)轉(zhuǎn)到kdis[k] = min(dis[k], dis[mark] + g[mark][k]); //取最小的距離}} }

Bellman-Ford算法

思路：

要讓以下等式成立
$$dis[v]=min(dist[v],dis[u]+e(u,v)|(u,v)\in E$$
其中 v是終點(diǎn)，u是起點(diǎn)。

變量說(shuō)明

//從頂點(diǎn)u到頂點(diǎn)v的權(quán)值為w的邊 struct edge {int u,v,w; } edge es[maxn] ;//儲(chǔ)存所以邊 int dis[maxn]; //最短距離 int V,E; //頂點(diǎn)數(shù)、邊數(shù)

初始化

如果s是源點(diǎn)（起點(diǎn))則dis[s] = 0,之外，其余為INF（足夠大的常數(shù)）

完整代碼

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> //#include<unordered_map> #include<ctime> using namespace std; typedef long long ll; #define pi pair<int,int> #define mst(ss,b) memset(ss,b,sizeof(ss)); #define rep(i,k,n) for(int i=k;i<=n;i++) #define INF 0x3f3f3f3fconst ll maxn = 2e5 + 10; //從頂點(diǎn)u到頂點(diǎn)v的權(quán)值為w的邊 struct edge {int u, v, w; }; edge es[maxn];//儲(chǔ)存所有邊 int dis[maxn]; //最短距離 int V, E; //頂點(diǎn)數(shù)、邊數(shù)//求解從頂點(diǎn)s出發(fā)到所以點(diǎn)的最短距離void Bellman_Ford(int s) {for (int i = 0; i < V; ++i)dis[i] = INF;dis[s] = 0;//對(duì)每一條邊進(jìn)行V-1次松弛for (int i = 0; i < V; ++i){for (int j = 0; j < E; ++j){edge e = es[j];if (dis[e.v] > dis[e.u] + e.w)dis[e.v] = dis[e.u] + e.w;}}}

• 為什么是V-1次呢？
  因?yàn)橐粋€(gè)含有n個(gè)頂點(diǎn)的圖中，任意兩個(gè)頂點(diǎn)之間的最短路徑最多包含n-1條邊，

Bellman-Ford 檢測(cè)圖是否含有負(fù)圈（回路）

思路

如果進(jìn)行了V-1 次（V為頂點(diǎn)數(shù)）松弛后還可以進(jìn)行松弛就表明存在負(fù)圈

代碼

在上面的Bellman-Ford基礎(chǔ)上，

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> //#include<unordered_map> #include<ctime> using namespace std; typedef long long ll; #define pi pair<int,int> #define mst(ss,b) memset(ss,b,sizeof(ss)); #define rep(i,k,n) for(int i=k;i<=n;i++) #define INF 0x3f3f3f3fconst ll maxn = 2e5 + 10; //從頂點(diǎn)u到頂點(diǎn)v的權(quán)值為w的邊 struct edge {int u, v, w; }; edge es[maxn];//儲(chǔ)存所以邊 int dis[maxn]; //最短距離 int V, E; //頂點(diǎn)數(shù)、邊數(shù)//求解從頂點(diǎn)s出發(fā)到所以點(diǎn)的最短距離void Bellman_Ford(int s) {for (int i = 0; i < V; ++i)dis[i] = INF;dis[s] = 0;//對(duì)每一條邊進(jìn)行V-1次松弛for (int i = 0; i < V; ++i){for (int j = 0; j < E; ++j){edge e = es[i];if (dis[e.v] > dis[e.u] + e.w)dis[e.v] = dis[e.u] + e.w;}}}bool neg_cir() {bool flag = false;for (int i = 0; i < E; ++i){edge e = es[i];if (dis[e.v] > dis[e.u] + e.w){flag = true;break;}}return flag; }

Bellman-Ford 算法優(yōu)化

在實(shí)際操作中，Bellman-Ford 算法經(jīng)常會(huì)未達(dá)到 n - 1輪松弛前就已經(jīng)計(jì)算出所有最短路，之前我們已經(jīng)說(shuō)過(guò)，n - 1其實(shí)是最大值。因此我們需要變量判斷一下下輪循環(huán) dis中的值是否改變，可以提前跳出循環(huán)，提高效率，基本優(yōu)化如下：

void Bellman_Ford(int s) {for (int i = 0; i < V; ++i)dis[i] = INF;dis[s] = 0;while (true){bool update = false; //檢測(cè)是否有更新for (int i = 0; i < E; ++i){edge e = es[i];//如果起點(diǎn)到 e.u 距離為 INF 就說(shuō)明無(wú)法松弛了if (dis[e.u] != INF && dis[e.v] > dis[e.u] + e.w) {dis[e.v] = dis[e.u] + e.w;update = true;}}//沒有的話就退出循環(huán)if (!update)break;}}

SPFA算法

思路

SPPA其實(shí)是Bellman-Ford的隊(duì)列優(yōu)化。我們用數(shù)組dits比錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，并用鄰接表來(lái)存儲(chǔ)圖g。我們采取的方法是松弛：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止。

只要最短路徑存在，上述SPFA算法必定能求出最小值。因?yàn)槊看螌Ⅻc(diǎn)放入隊(duì)尾，都是經(jīng)過(guò)松弛操作達(dá)到的。換言之，每次的優(yōu)化將會(huì)有某個(gè)點(diǎn)p的最短路徑估計(jì)值d[9]變小。所以算法的執(zhí)行會(huì)使d越來(lái)越小。由于我們假定圖中不存在負(fù)權(quán)回路，所以每個(gè)結(jié)點(diǎn)都有最短路徑值。因此，算法不會(huì)無(wú)限執(zhí)行下去，隨著d值的逐漸變小，直到到達(dá)最短路徑值時(shí)，算法結(jié)束，這時(shí)的最短路徑估計(jì)值就是對(duì)應(yīng)結(jié)點(diǎn)的最短路徑值。

完整代碼

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> //#include<unordered_map> #include<ctime> using namespace std; typedef long long ll; #define pi pair<int,int> #define mst(ss,b) memset(ss,b,sizeof(ss)); #define rep(i,k,n) for(int i=k;i<=n;i++) #define INF 0x3f3f3f3f const int N = 2e3 + 10;//也可以用結(jié)構(gòu)體 vector<pi> g[N];//鄰接表儲(chǔ)存所以邊，// g[i][j].first 表示i節(jié)點(diǎn)的第j條邊的編號(hào)（本來(lái)鄰接表的作用）//g[i][j].second 表示邊的長(zhǎng)度，權(quán)值 int dis[N];//表示 源點(diǎn)src到 i的最短距離 bool vis[N];//是否在集合中 int src;//源點(diǎn) int n, m;//n 頂點(diǎn)數(shù)，m邊數(shù) queue<int>q;void init() {for (int i = 0; i <= n; ++i)g[i].clear();mst(vis, 0); //初始化點(diǎn)的集合為空mst(dis, INF);//初始化距離為一個(gè)很大的數(shù)while (!q.empty())q.pop(); //將隊(duì)列清空 }void spfa() {init();//記得初始化dis[src] = 0;//自己到自己的距離肯定為1vis[src] = 1;//把源點(diǎn)存入集合中q.push(src); //將源點(diǎn)壓入隊(duì)列while (!q.empty()){int u = q.front(); //取出對(duì)首元素q.pop();for (int i = 0; i < g[u].size(); ++i){//這個(gè)語(yǔ)句和 Dijstra 中的// dis[k] 中 dis[k] 表示源點(diǎn)到 頂點(diǎn)k的距離(直接到k）//dis[mark] + g[mark][k] 先到當(dāng)前距離短的點(diǎn)mark，通過(guò)這個(gè)點(diǎn)轉(zhuǎn)到k//意思是一樣的if (dis[u] + g[u][i].second < g[u][i].first){//如果更小就更新g[u][i].first = dis[u] + g[u][i].second;if (!vis[g[u][i].first]) //不在集合中{//就加入vis[g[u][i].first] = 1;q.push(g[u][i].first);}}}//讓這個(gè)點(diǎn)還有進(jìn)入隊(duì)列的機(jī)會(huì)vis[u] = false;} }

算法的比較

總結(jié)

以上是生活随笔為你收集整理的最短路径（Dijkstra、Bellman-Ford和SPFA算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。