最短路径问题是图论中很重要的问题。

解决最短路径几个经典的算法

1、Dijkstra算法

单源最短路径（贪心），还有用 priority_queue 进行优化的 Dijkstra 算法。

2、bellman-ford算法

例题：【ACM】POJ 3259 Wormholes

允许负权边的单源最短路径算法

优点：可以发现负圈。缺点，时间复杂度比Dijkstra算法高。

算法流程：

（1）初始化：将除源点外的所有顶点的最短距离估计值d[v]趋于正无穷，d[start]=0

（2）迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点V中的每个顶点v的最短距离估计值逐步逼近其最短距离（运行|v|-1次）

（3）检验负权回路：判断边集E中的每一条边的两个顶点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解，否则算法返回true，并从源点可达的顶点v的最短距离保存在d[v]中。

Bellman-Ford(G,w,s) ：boolean   //图G ，边集 函数 w ，s为源点1        for each vertex v ∈ V（G） do        //初始化 1阶段2            d[v] ←+∞3        d[s] ←0;                             //1阶段结束4        for i=1 to |v|-1 do               //2阶段开始，双重循环。5           for each edge（u,v） ∈E(G) do //边集数组要用到，穷举每条边。6              If d[v]> d[u]+ w(u,v) then      //松弛判断7                 d[v]=d[u]+w(u,v)               //松弛操作   2阶段结束8        for each edge（u,v） ∈E(G) do9            If d[v]> d[u]+ w(u,v) then10            Exit false11    Exit true

3、SPFA

是bellman-ford + 队列优化，其实和bfs关系更密

4、floyd算法

多元最短路算法，是一个经典的动态规划算法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

题目大意是：已知顶点数n，边数及权值，求第1个点到第n个点的最短路的长度

有很多种解法

1、Dijkstra

推荐博客：【算法】【ACM】深入理解Dijkstra算法（单源最短路径算法）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 9999999;
int map[105][105];
int d[105];
bool vis[105];
int N,M;void dijkstra()
{int i,j,min,pos;for(i=1;i<N;i++){min = INF;for(j=1;j<=N;j++){if(!vis[j] && d[j]<min){min = d[j];pos = j;}}if(min == INF)return ;vis[pos] = true;for(j=1;j<=N;j++){if(!vis[j] && (min+map[pos][j]<d[j])){d[j] = map[pos][j] + min;}}}
}int main()
{int i,j,a,b,t;while(scanf("%d%d",&N,&M)!=EOF){if(N==0 && M==0)return 0;for(i=0;i<=N;i++){for(j=0;j<=N;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = INF;}}for(i=0;i<M;i++){cin >> a >> b >> t;if(t < map[a][b]){map[a][b] = t;map[b][a] = t;}}memset(vis,false,sizeof(vis));for(i=1;i<=N;i++)d[i] = map[1][i];vis[1] =true;dijkstra();cout << d[N] << endl; }return 0;
}

2、Floyd 算法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 9999999;
int map[105][105];int main ()
{int n,m;int a,b,c;int i,j,k;while (scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)return 0;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = maxn;}}for(i=1;i<=m;i++){cin >> a >> b >> c;if(map[a][b] > c){map[a][b] = map[b][a] = c;}}for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++){map[i][j] = min(map[i][j],map[i][k]+map[k][j]);}}}cout << map[1][n] << endl;}return 0;
}

3、Dijkstra + 优先队列 （邻接矩阵表示）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <functional>
using namespace std;typedef pair<int,int> p;
const int maxn = 9999999;
int N,M;
int d[105];
bool vis[105];
int map[105][105];void dijkstra()
{int i;memset(vis,false,sizeof(vis));memset(d,maxn,sizeof(d));d[1] = 0;priority_queue<p,vector<p>,greater<p> > q;q.push(make_pair(d[1],1));while(q.empty()!=1){p p1=q.top();q.pop();int pos = p1.second;if(vis[pos])continue;vis[pos] = true;for(i=2;i<=N;i++){if(!vis[i] && d[i]>map[pos][i]+d[pos]){d[i] = map[pos][i]+d[pos];q.push(make_pair(d[i],i));}}}
}int main ()
{int i,j;while(scanf("%d%d",&N,&M)!=EOF){if(N==0 && M==0)return 0;for(i=0;i<=N;i++){for(j=0;j<=N;j++){if(i==j)    map[i][j] = 0;else    map[i][j] = maxn;}}int a,b,c;for(i=0;i<M;i++){cin >> a >> b >> c;if(map[a][b] > c){map[a][b] = c;map[b][a] = c;}}dijkstra();cout << d[N] << endl;}return 0;
}

4、Dijkstra + 优先队列 + vector（邻接表表示）

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
using namespace std;
typedef pair<int,int> p;//first是最短距离，second是顶点编号
const int maxn = 9999999;struct edge
{int to;//邻接的点int cost;//以及到该点的权值
};vector<edge> eg[105];//邻接表
bool vis[105];//表示是否已经使用过
int d[105];//最短距离
int n,m;//顶点数和边数void dijkstra()
{//priority_queue，优先队列按first由小到大，默认的是从大到小priority_queue<p,vector<p>,greater<p>> q;//初始化memset(d,maxn,sizeof(d));memset(vis,false,sizeof(vis));d[1] = 0;q.push(p(d[1],1));while(q.empty()!=1){p p1 = q.top();q.pop();int pos = p1.second;if(vis[pos])continue;vis[pos] = true;for(int i=0;i<eg[pos].size();i++){edge x = eg[pos][i];if(d[x.to] > d[pos] + x.cost){//起点到x的距离与 选中的这个pos点+pos到x的距离和 作比较d[x.to] = d[pos] + x.cost;q.push(p(d[x.to],x.to));}}}
}int main ()
{while(scanf("%d%d",&n,&m)!=EOF){int i;if(n==0 && m==0)return 0;for(i=1;i<=n;i++)eg[i].clear();int a,b,c;for(i=1;i<=m;i++){cin >> a >> b >> c;edge g1,g2;//无向图的缘故g1.to = b;g1.cost = c;g2.to = a;g2.cost = c;eg[a].push_back(g1);eg[b].push_back(g2);}dijkstra();cout <<d[n] << endl;}return 0;
}

5、bellman_ford（邻接矩阵）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 9999999;
int d[105];
int map[105][105];
int n,m;void bellman_ford()
{memset(d,maxn,sizeof(d));d[1] = 0;int flag = 1;int k,i,j;for(k=0;k<n-1 && flag;k++){flag = 0;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if( map[i][j] && d[i]!=maxn && (d[j]>map[i][j]+d[i]) ){d[j] = map[i][j]+d[i];flag = 1;}}}if(flag == 0)return ;}
}int main()
{int i,j;int a,b,c;while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)return 0;for(i=0;i<=n;i++){for(j=0;j<=n;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = maxn;}}for(i=1;i<=m;i++){cin >> a >> b >> c;if(map[a][b] > c){map[a][b] = c;map[b][a] = c;}}bellman_ford();cout << d[n] << endl;}return 0;
}

用边表示

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 9999999;typedef struct Edge
{int u,v;int weight;
}Edge;
Edge edge[10000+10]; 
int d[105];
int n,m;void bellman_ford()
{int flag = 1,i,j;for(i=1;i<=n-1 && flag;i++){flag = 0;//因为是无向图，所以是双向的for(j=1;j<=m;j++){if(d[edge[j].v]>d[edge[j].u]+edge[j].weight){d[edge[j].v]=d[edge[j].u]+edge[j].weight;flag = 1;}if(d[edge[j].u]>d[edge[j].v]+edge[j].weight){d[edge[j].u]=d[edge[j].v]+edge[j].weight;flag = 1;}}if(!flag)return ;}
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)return 0;memset(d,maxn,sizeof(d));d[1] = 0;for(int i=1;i<=m;i++){cin >> edge[i].u >> edge[i].v >> edge[i].weight;//注意这里设置初始情况if(edge[i].u==1){d[edge[i].v] = edge[i].weight;}}bellman_ford();cout << d[n] << endl;}return 0;
}

6、SPFA（邻接矩阵）因为这个题目不存在负权边，所以就没有记录每个点的入队次数

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 9999999;
int n,m;
int map[105][105];
int d[105];
int vis[105];void SPFA()
{memset(vis,false,sizeof(vis));memset(d,maxn,sizeof(d));queue<int> Q;Q.push(1);d[1] = 0;vis[1] = true;int v;while(Q.empty()!=1){int u = Q.front();Q.pop();vis[u] = false;for(v=1;v<=n;v++){if(map[u][v]!=maxn){if(d[u]+map[u][v]<d[v]){d[v] = map[u][v]+d[u];if(!vis[v]){Q.push(v);vis[v] = true;}}}}}
}int main ()
{int i,j;while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)return 0;for(i=0;i<=n;i++){for(j=0;j<=n;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = maxn;}}int a,b,c;for(i=1;i<=m;i++){cin >> a >> b >> c;if(map[a][b]>c){map[a][b] = c;map[b][a] = c;}}SPFA();cout << d[n] << endl;}return 0;
}

用边来表示

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;struct Edge
{int s,e,w;Edge(){s = -1;e = -1;w = -1;}
};const int maxn = 9999999;
Edge edge[10000+10];
int n,m;
int d[105];
int vis[105];
int all_e;void SPFA()
{memset(vis,0,sizeof(vis));memset(d,maxn,sizeof(d));d[1] = 0;vis[1] = true;queue<int> Q;Q.push(1);int v;while(Q.empty()!=1){int u = Q.front();Q.pop();vis[u] = false;for(v=0;v<all_e;v++){if(d[edge[v].e]>d[edge[v].s]+edge[v].w){d[edge[v].e]=d[edge[v].s]+edge[v].w;if(!vis[edge[v].e]){Q.push(edge[v].e);vis[edge[v].e] = true;}}}}
}int main ()
{int i;while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)return 0;all_e = 0;int a,b,c;for(i=0;i<m;i++){cin >> a >> b >> c;edge[all_e].s = a;edge[all_e].e = b;edge[all_e++].w = c;edge[all_e].s = b;edge[all_e].e = a;edge[all_e++].w = c;}SPFA();cout << d[n] << endl;}return 0;
}