最短路徑算法(算法篇)

算法之最短路徑算法

最短路徑算法

概念：

考查最短路徑問題，可能會輸入一個賦權圖(也就是邊帶有權的圖)，則一條路徑的v1v2…vN的值就是對路徑的邊的權求和，這叫做賦權路徑長，如果是無權路徑長就是單純的路徑上的邊數。
在賦權圖，可能會出現負值邊的情況，這樣當我們去找最短路徑時，可能會產生負值圈，畢竟一直走負值邊可以將數值變得更短。

單源最短路徑問題：

給定一個賦權圖G=(V,E)和一個特定頂點s作為輸入，找出從s到G中每一個其他頂點的最短賦權路徑。

無權最短路徑：

給定一個無權圖G=(V,E)和一個起始頂點s作為輸入，找出從s到G中每一個其他頂點的最短路徑。

廣度優先搜索算法(BFS)

概念：

廣度優先搜索算法(BFS)用于在無權圖或者邊權相同的圖中尋找最短路徑。
該方法按層處理頂點，首先從起始點出發，進行發散找到與起始點鄰接的頂點a,…，并將s到這些頂點的路徑距離更新，然后將該點標記成已經訪問的頂點并將該點的前一個頂點記錄下來(被標記的頂點我們后面遇到就認為該點已經不需要再進行處理了)，然后再從頂點a,…發散，找到該頂點的鄰接頂點，然后重復操作，直到所有頂點都被標記完，就完成了搜索。
具體代碼實現，是用一個隊列，在迭代開始時，隊列中只含有距離為迭代距離currdist的那些頂點，然后執行操作時，將距離currdist+1的頂點的那些頂點添加到隊列中，只要當前距離為currdist頂點處理完，就會處理距離為currdist+1(也就是當前頂點發散的頂點)的頂點添加到隊列中。
在隊列中其實可以將know域也就是標記去掉，因為隊列的形式已經說明執行過了，就不會在執行，因此相當于標記了。

代碼：

//圖的鄰接表的結點信息
struct listnode{int data;bool flag;    //判斷是否訪問過int path;     //存儲上一個頂點int dist;     //距離listnode* next;
};//圖的信息
class graph{
private:listnode *an;   //鄰接表形式存儲圖int vnum;     //圖中結點數
};//s為起點，an數組的鄰接表表示圖
void BFS(int s){queue<int>q;q.push(s);an[s].dist=0;while (!q.empty()){int v=q.front();q.pop();an[v].flag= true;listnode* p=an[v].next;while (p!= nullptr){if(an[p->data].dist==INT_MAX){an[p->data].dist=an[v].dist+1;an[p->data].path=v;q.push(p->data);}p=p->next;}}}

Dijkstra算法

概念：

用于求解賦權圖的最短路徑(無負值邊)，Dijkstra算法是解決單源最短路徑問題的一般方法，并且該解法是貪心算法。Dijkstra只是BFS的升級版使他能夠求賦權圖的最短路徑，如果求無權圖Dijkstra跟BFS的做法一樣！
Dijkstra算法是分階段的，該算法認為每一個階段，都將該階段當作最好的情況處理，類似于BFS算法，但是還是有不同的地方，比起BFS多出了需要進行每個階段出現最好情況就進行更新路徑。
具體做法是，從圖中選取起始點v，然后找出鄰接點，并將當前起始點到鄰接點v3,v4…的距離更新，如果是賦權圖就是dv+C_v,v3(就是頂點v到v3的權)，如果是無權就是dv+1，并將v標記為已知。然后選取鄰接點集中的一點再做為起始點，然后重復操作，將當前頂點的前一個頂點記錄。當v到某個頂點的距離在當前階段是最小的(最好情況)，那么就進行更新，如果不是就無需更新。
具體來說，當我們擴展一個新結點時，我們會考慮它的所有未訪問過的鄰接結點，并計算從起始結點經過當前結點到達鄰接結點的路徑長度。如果這個長度小于已知的最短路徑長度（或者鄰接結點的路徑長度尚未初始化），我們就更新鄰接結點的路徑長度。這樣做的目的是通過不斷更新路徑長度來找到起始結點到所有其他結點的最短路徑。
實現的時候可以使用優先隊列來進行優化算法，只將頂點和其最短路徑值進入隊列中當隊列非空，執行以下操作：u等于隊頂的節點，w等于隊頂節點的最短路徑值；遍歷u的所有邊，如果能找到節點v最短路徑值小于v的當前值，更新v，將v壓入隊列。結束
沒有用優先隊列優化的Dijkstra算法的時間復雜度為O(N2)，如果使用優先隊列，則時間復雜度為O(nlogn)，可以不用考慮已知域;

Dijkstra跟BFS區別：

處理頂點：
- 在BFS算法中，當一個頂點被擴展時，它的所有未訪問過的鄰居頂點都被添加到隊列中，這樣它們將按照遍歷的順序逐個被訪問。
- 在Dijkstra算法中，當一個頂點被擴展時，它的鄰居頂點也被考慮，但是Dijkstra算法會計算擴展的頂點與其鄰居之間的邊的權重，并根據這個權重來更新到達鄰居頂點的最短路徑長度。這個更新過程使得Dijkstra算法能夠處理帶有非負權重的圖。
選擇下一個頂點：
- 在BFS算法中，下一個要被擴展的頂點是隊列中的下一個頂點，也就是按照隊列的先進先出（FIFO）原則選擇。
- 在Dijkstra算法中，下一個要被擴展的頂點是距離起始點路徑長度最小的頂點，也就是根據已知的最短路徑長度來選擇。這需要使用優先隊列或者最小堆來高效地選擇路徑長度最小的頂點。

代碼：

//圖的鄰接表的結點信息
struct listnode{int data;int path;     //存儲上一個頂點int dist;     //最短距離int weight;   //數組索引頂點跟該頂點的邊的權重listnode* next;
};//圖的信息
class graph{
private:listnode *an;   //鄰接表形式存儲圖int vnum;     //圖中結點數
};//v是起始點
void Dijkstra(int v){an[v].dist=0;queue<int>q;q.push(v);while (!q.empty()){int w=q.front();q.pop();listnode* p=an[w].next;while (p!= nullptr){if(an[w].dist+p->weight<an[p->data].dist){an[p->data].dist=an[w].dist+p->weight;an[p->data].path=w;q.push(p->data);}p=p->next;}}}

題目模板：
有向邊單源最短路徑問題

#include <bits/stdc++.h>
using namespace std;const int INF=0x3f3f3f3f;const int N=10;
int n;struct edge {int v, w;
};bool vis[N+1];int dijkstra(int start, const vector<vector<edge>>& graph) {int minroad[n+1];memset(minroad,INF,sizeof minroad);minroad[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, start});while (!pq.empty()) {auto [d, u] = pq.top();pq.pop();if(vis[u]) continue;vis[u]=true;for (const auto& edges : graph[u]) {int v = edges.v;int w = edges.w;if (minroad[u] + w < minroad[v]) {minroad[v] = minroad[u] + w;pq.push({minroad[v], v});}}}return minroad[n]!=INF?minroad[n]:-1;
}int main() {int m, start;cin >> n >> m >> start;vector<vector<edge>> graph(n + 1);for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;graph[u].push_back({v, w});}cout<<dijkstra(start, graph)<<endl;system("pause");return 0;
}

Floyd算法

概念：

Floyd(弗洛伊德)算法是基于動態規劃思想的算法，也稱插點法，是全源最短路算法(全源就代表經過一次Floyd算法，每個點到各個點的最短路徑都能算出來)
用于求任意一對頂點間的最短路徑，此時圖中的邊的權值可以出現負數，但不能出現負環
時間復雜度為O(n3)，n為點個數

基本思想：

對于從i到j的弧，進行n次試探
首先考慮i，0，j是否存在，如果存在，則比較i，j和i，0，j的路徑長度，去最短者進行更新i，j的最短路徑
然后再添加頂點1，依次類推。

具體過程：

當一個圖里有n個城市，求全源最短路徑問題
定義城市k為從當前圖拿出來，并重新插入圖中的城市，城市i，城市j分別為當前源城市和目的城市。dist[i\][j]表示城市i到城市j的最短路徑
假設當前圖中沒有城市k，我們將城市k重新插入到圖中
我們需要判斷城市i到城市j的最短路徑是否要更新，則比較路徑經過城市k和原來的路徑長度進行比較，如果經過城市k的路徑長度更短，則更新dist[i][j]，因此就為dist[i][j]=min(dist[i][k]+dist[k][j],dist[i][j])
因此對這個圖執行n次上述操作(也就是插點法)，得出的dist二維數組就為全源的最短路徑。

代碼模板：

//dist[n][n]用來記錄圖中各點到各點的最短路徑
void Floyd(int **dist){for(int k=0;k<n;++k){for(int i=0;i<n;++i){for(int j=0;j<n;++j){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}
}

例題部分代碼：

具體可看力扣1334. 閾值距離內鄰居最少的城市，只包含求解全源最短路徑代碼

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;void Floyd(int n, vector<vector<int>>& edges){const int INF=0x3f3f3f3f;int dist[n][n];memset(dist,INF, sizeof(dist));for(int i=0;i<n;++i){dist[i][i]=0;}for(auto edge:edges){dist[edge[0]][edge[1]]=edge[2];dist[edge[1]][edge[0]]=edge[2];}//Floyd算法計算全源最短路代碼for(int k=0;k<n;++k){for(int i=0;i<n;++i){for(int j=0;j<n;++j){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}for(int i=0;i<n;++i){cout<<"第"<<i<<"城市到其他城市最短路徑：";for(int j=0;j<n;++j)cout<<"("<<i<<","<<j<<","<<dist[i][j]<<")"<<" ";cout<<endl;}
}int main() {vector<vector<int>>edges{{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}};Floyd(5,edges);system("pause");return 0;
}