最短路徑

1.Dijkstra算法

主要解決單源最短路徑問題：

void Dijkstra(int s){for(int i = 0;i < maxn;i++)dis[i] = INF;dis[s] = 0;for(int i = 0;i < n;i++){int u = -1,min = INF;for(int j = 0;j < n;j++){if(!visit[j] && dis[j] < INF){u = j;min = dis[j];}}if(u == -1) return;visit[u] = true;for(int j = 0;j < n;j++){if(!visit[j] && G[u][j] != INF){if(dis[j] > dis[u] + G[u][j]){dis[j] = dis[u] + G[u][j];}}}}}

當(dāng)有兩種或以上的最短路徑時，一般情況下題目就會給出一個第二標(biāo)尺，常見如下：

新增邊權(quán)，以新增的邊權(quán)代表花費(fèi)為例，用cost[u][v]表示 U -> V 的花費(fèi)，并新增一個數(shù)組c[]，令從起點(diǎn)s到達(dá)u的最小花費(fèi)為c[u]，初始化時只有c[s]為0、其余均為INF。

當(dāng)有兩種或以上的最短路徑時，一般情況下題目就會給出一個第二標(biāo)尺，常見如下：

新增邊權(quán)，以新增的邊權(quán)代表花費(fèi)為例，用cost[u][v]表示 U -> V 的花費(fèi)，并新增一個數(shù)組c[]，令從起點(diǎn)s到達(dá)u的最小花費(fèi)為c[u]，初始化時只有c[s]為0、其余均為INF。

for(int v = 0;v < n;v++){if(visit[v] == false && G[u][v] != INF){if(d[u] + G[u][v] < d[u]){d[v] = d[u] + G[u][v];cost[v] = c[u] + cost[u][v];}else if(d[u] + G[u][v] == d[u] && c[u] + cost[u][v] < c[v]){c[v] = c[u] + cost[u][v];}}}

新增點(diǎn)權(quán)，以新增的點(diǎn)權(quán)代表城市中能收集到的物資為例，用weight[u]表示城市 u 中的物資數(shù)目，并新增一個數(shù)組w[]，令從起點(diǎn)s到達(dá)u的能收集的最大物資為w[u]，初始化時只有w[s] = weight[s]，其余均為0 。

for(int v = 0;v < n;v++){if(visit[v] == false && G[u][v] != INF){if(d[u] + G[u][v] < d[u]){d[v] = d[u] + G[u][v];w[v] = w[u] + weight[v];}else if(d[u] + G[u][v] == d[u] && c[u] + cost[u][v] < c[v]){w[v] = w[u] + weight[v];}}}

求最短路徑條數(shù)，只需要增加一個數(shù)組num[]，令起點(diǎn)s到達(dá)頂點(diǎn)u的最短路徑條數(shù)為num[u]，這樣初始化時只有num[s] = 1、其余 num[s] 均為0 。

for(int j = 0;j < n;j++){if(visit[j] == false && G[u][j] != INF){if(dis[j] > dis[u] + G[u][j]){ //如果能找到更短的路徑就更新 dis 數(shù)組dis[j] = dis[u] + G[u][j]; num[j] = num[u];}else if(dis[j] == dis[u] + G[u][j]){ //找到一條長度相等的路徑num[j] += num[u]; }}}

2.Bellman-Ford算法

　　Dijkstra 算法可以很好的解決無負(fù)權(quán)圖的最短路徑問題，但如果出現(xiàn)了負(fù)邊權(quán)，Dijkstra就會失效，為了更好地求解有負(fù)權(quán)的最短路徑問題，需要使用Bellman-Ford算法，Bellman-Ford算法可以解決單源最短路徑問題，但也能處理有負(fù)權(quán)邊的情況。

#include <iostream>#include <vector>using namespace std;const int maxn = 500 + 5;const int INF = 1000000000;int dis[maxn];struct node{int v,d;//鄰結(jié)點(diǎn)和鄰接邊的邊權(quán)node(int v1,int d1):v(v1),d(d1) {}};int n,m;vector <node> Adj[maxn];bool Ford(int s){for(int i = 0;i < maxn;i++)dis[i] = INF;dis[s] = 0;for(int i = 0;i < n-1;i++){for(int u = 0;u < n;u++)for(int j = 0;j < Adj[u].size();j++){int v = Adj[u][j].v;//鄰接邊的頂點(diǎn)int d = Adj[u][j].d;//鄰接邊的邊權(quán)if(dis[u] + d < dis[v]){dis[v] = dis[u] + d;}}}//以下為判斷負(fù)環(huán)的代碼for(int u = 0;u < n;u++)for(int j = 0;j < Adj[u].size();j++){int v = Adj[u][j].v;int d = Adj[u][j].d;if(dis[u] + d < dis[v]){//如果仍可以被松弛return false; //說明圖中有從源點(diǎn)可達(dá)的負(fù)環(huán)}}return true;}int main(void){int v1,v2,s,d;cin>>n>>m>>s;cin>>v1>>v2>>d; //負(fù)權(quán)值是單向的Adj[v1].push_back(node(v2,d));for(int i = 0;i < m-1;i++){cin>>v1>>v2>>d;Adj[v1].push_back(node(v2,d));Adj[v2].push_back(node(v1,d));}if(Ford(s)){cout<<"該圖中沒有負(fù)環(huán)。"<<endl;}else{cout<<"該圖中存在負(fù)環(huán)。"<<endl;}for(int i = 0;i < n;i++)cout<<dis[i]<<" ";cout<<endl;return 0;}/*3 3 00 1 -30 2 11 2 53 3 00 1 -30 2 11 2 23 3 00 1 -30 2 11 2 1*/

3.SPFA算法

　　SPFA算法是Bellman-Ford算法優(yōu)化的結(jié)果

vector <node> Adj[maxn];bool SPFA(int s){for(int i = 0;i < maxn;i++)dis[i] = INF;dis[s] = 0;memset(num,0,sizeof(num);queue <int> q;q.push(s);visit[s] = true;num[s]++;while(!q.empty()){int u = q.front();q.pop();visit[u] = false; //不在隊(duì)列中for(int i = 0;i < Adj[u].size();i++){int v = Adj[u][i].v;//鄰接邊的頂點(diǎn)int d = Adj[u][i].d;//鄰接邊的邊權(quán)//松弛操作if(dis[v] > dis[u] + d){dis[v] = dis[u] + d;if(!visit[v]){q.push(v);num[v]++;//當(dāng)前結(jié)點(diǎn)入隊(duì)次數(shù)加一visit[v] = true;if(num[v] >= n) return false; //有可達(dá)的負(fù)環(huán)}}}}return true;}

4.Floyd算法

　　Floyd 算法用來解決全源最短路徑問題，即對給定的圖G(V,E)，求任意兩點(diǎn)u,v之間的最短路徑長度。

void Floyd(){for(int k = 0;k < n;k++) //輔助頂點(diǎ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){if(dis[i][j] > dis[i][k] + dis[k][j]){dis[i][j] = dis[i][k] + dis[k][j];}}}}

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的最短路径 的一些解法和特殊情况的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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