最短路徑問題

• 1、Dijkstra算法
• • 簡介
  • （1）Dijkstra算法偽代碼
  • （2）C++ 鄰接表版代碼
  • （3）優化
  • （4）題型分析
• 2、Bellman Ford算法
• • 簡介
  • （1）Bellman算法偽代碼
  • （2）C++ 鄰接表版代碼
• 3、SPFA算法
• • 簡介
  • （1）SPFA算法偽代碼
  • （2）C++ 鄰接表版代碼

1、Dijkstra算法

簡介

Dijkstra算法用于計算單源最短路徑，即給定圖G(V,E)以及源點s，求s到其他頂點的最短路徑。
時間復雜度：

（1）Dijkstra算法偽代碼

dijkstra (G,s){初始化變量for 循環遍歷n次{u為未訪問過的節點中離s最近的頂點如果不存在u，那么表示剩余節點與s不連通，return;訪問ufor 遍歷所有與u相連的頂點v{if 如果d[u] + dis<d[v]：證明經過u能夠使源點s到頂點v距離更短！更新d[v] = d[u] + dis}} }

（2）C++ 鄰接表版代碼

//Dijstra算法 #include <iostream> #include <algorithm> #include <cstring> #include <vector>using namespace std;struct Node {int v, dis;Node(int _v, int _dis) {v = _v;dis = _dis;} };const int MAXV = 1000; const int INF = 0x3fffffff; int n, m, st, ed; vector<Node> Adj[MAXV]; int d[MAXV]; bool vis[MAXV];//是否訪問過void dijkstra(int st) { //起點fill(d, d + MAXV, INF);d[st] = 0;memset(vis, false, sizeof vis);for (int i = 0; i < n; i++) {int u = -1; // 找出一個最短的地點攻占int min_distance = INF;for (int j = 0; j < n; j++) {if (vis[j] == false && d[j] < min_distance) {min_distance = d[j];u = j;}}if (u == -1) {//如果找不到小于INF的d[u]，說明剩下的節點與s不連通return;}vis[u] = true;for (int j = 0; j < Adj[u].size(); j++) {int v = Adj[u][j].v;if (vis[v] == false && d[u] + Adj[u][j].dis < d[v]) {d[v] = d[u] + Adj[u][j].dis;}}} }int main() {cin >> n >> m >> st >> ed; //n個頂點 m條邊int a, b, wt;for (int i = 0; i < m; i++) {cin >> a >> b >> wt;Adj[a].push_back(Node(b, wt));//Adj[b].push_back(Node(a, wt)); //無向圖時加上}dijkstra(st);for (int i = 0; i < n; i++) {cout << d[i] << endl;}return 0; }

（3）優化

1）采用堆排序2）使用STL中的set3）使用STL中的prority queue （優先隊列） 時間復雜度降到O(VlogV+E）

（4）題型分析

在實際問題中，可能會存在有兩條及以上可達到的最短路徑，于是，題目會給出第二標尺（第一標尺是距離），要求在所有最短路徑中根據給定的第二標尺選擇最優的一條路徑。第二標尺通常情況是以下三種出題方式或者組合：

1）給每條邊增加一個 邊權 （比如說花費），比如說花費最小或者其他含義的邊權要求最大。2）給每個頂點增加一個 點權 （比如每個城市能夠收集的物資），要求在最短路徑下收集的物資最多。其他含義也可能求最小。3）直接問有多少條最短路徑。

解決：待更新 提示：增加一個pre數組
訪問路徑？？？DFS

2、Bellman Ford算法

簡介

Dijkstra算法可以很好的解決無負權圖的最短路徑問題，但如果出現了負權邊Dijkstra算法就會失效。
為了更好的解決帶有負權邊的最短路徑問題，需要使用Bellman Ford算法。
環：根據環中的邊權之和的正負，可以將環分為零環、正環和負環。
如果圖中存在負環，且從源點可達，那么會影響最短路徑的求解！

（1）Bellman算法偽代碼

時間復雜度：
采用鄰接表 – O(VE)
采用鄰接矩陣 – O(V^3)

for 循環V-1輪（因為搜索樹的深度不能超過V-1，否則圖中有回路存在。）{循環每一條邊 u->v for (int u =0;u<n;u++) { //對于頂點ufor(int j=0;j<Adj[u].size();j++){//遍歷與u連接的每一條邊int v = Adj[u][j].v;int dis = Adj[u][j].dis;if 如果d[u]+dis<d[v]://松弛操作更新d[v]=d[u]+dis;}} }

（2）C++ 鄰接表版代碼

3、SPFA算法

簡介

雖然Bellman Ford算法很好的解決了負權值的問題，但由于它要遍歷所有的邊，時間復雜度著實有點高了。認真思考后會發現，只有當d[u]的值改變了，與之相連的v點 d[v]才有可能改變。根據該發現進行一個小的優化：建立一個隊列，每次取出隊首頂點u，對u出發的所有邊u->v進行松弛操作【即判斷d[u]+dis < d[v]，對d[v]進行優化。此時如果v不在隊列中，就將其加入隊列。因為d[v]改變了，與之相連的邊也可能改變。】直到隊列為空（說明圖中沒有后從源點可達的負權），或者是某個頂點的入隊次數超過V-1（說明圖中存在從源點可達的負環）。

（1）SPFA算法偽代碼

創建隊列q 源點入隊 當隊列不為空時：取出隊首元素ufor 循環遍歷u為起點的每一條邊v：if d[u]+dis<d[v]:更新d[v]if v 不在隊列中： 將其加入隊列num[v] += 1 //訪問次數加一如果v的訪問次數大于V-1：表示圖中存在源點可達的負權。 核心代碼： queue<Node> q; q.push(st);//源點入隊 num[st] += 1 //st訪問次數加一 inq[st] = true;//st在隊列中 while q.empty()!=null:u = q.front();q.pop(); //取出隊首元素uinq[u] = false;for(int i=0;i<Adj[u].size();i++){int v = Adj[u][i].v;int dis = Adj[u][i].dis;if d[u]+dis<d[v]:d[v] = d[u]+dis;if inq[v]!=true:q.push(v);num[v] += 1if num[v] >= V:return false;}

（2）C++ 鄰接表版代碼

總結

以上是生活随笔為你收集整理的最短路径：Dijkstra、BellmanFord以及SPFA算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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