最短路算法（Dijkstra、SPFA、Floyd，vector存边和链式向前星存边）

最短路算法（Dijkstra、SPFA、Floyd，vector存边和链式向前星存边）

最短路

∙ bullet ∙在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output

3
2

1.迪杰斯特拉算法

∙ bullet ∙算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
∙ bullet ∙vector存边

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<queue>
#include<string>
using namespace std;
const int maxn=110;
const int inf=999999999;
int n,m,vis[maxn]；//标记是否走过
int d[maxn];//d[i]表示i点到起点的最短距离
struct node
{int to,val;node (int a ,int b ):to(a),val(b){}
};
vector<node>v[maxn];
void init()
{for(int i=1;i<=n;i++)v[i].clear();memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)d[i]=inf;
}
void dij(int start)
{d[start]=0;for(int i=1;i<=n;i++){int minpos=-1;for(int j=1;j<=n;j++){//从没被标记过的集合里遍历找到d[i]最小的点if((vis[j]==0)&&(minpos<0||d[j]<d[minpos])){minpos=j;}}vis[minpos]=1;for(unsigned int i=0;i<v[minpos].size();i++){//遍历与刚才找出的最小点有边相连的点，并更新到起点的值int next=v[minpos][i].to;int val=v[minpos][i].val;if(d[minpos]+val<d[next])d[next]=d[minpos]+val;}}
}int main()
{while(scanf("%d%d",&n,&m)&&n+m){int a,b,val;init();for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&val);v[a].push_back(node(b,val));//双向边v[b].push_back(node(a,val));}dij(1);printf("%dn",d[n]);}return 0;
}

∙ bullet ∙链式向前星存边
附上学习链式向前星的博客（学长讲的跟本没听懂。。。）大佬写的博客在这

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int inf=999999999;
const int maxn = 2e4+10;
int cnt=0;
int n,m,vis[maxn],d[maxn];
struct node
{int to,val,next;
}edge[maxn*2];int head[maxn];
void add(int s,int e,int val)//链式向前星加边模板
{edge[++cnt]=node{e,val,head[s]};head[s]=cnt;
}void init()
{memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)d[i]=inf;memset(head,-1,sizeof(head));
}
void dij(int start)
{d[start]=0;for(int i=1;i<=n;i++){int minpos=-1;for(int j=1;j<=n;j++){if((vis[j]==0)&&(minpos<0||d[j]<d[minpos]))minpos=j;}vis[minpos]=1;if(d[minpos]==inf)break;for(int i=head[minpos];i!=-1;i=edge[i].next){//遍历与minpos有边的点if(d[minpos]+edge[i].val<d[edge[i].to])d[edge[i].to]=d[minpos]+edge[i].val;}}
}
int main()
{int a,b,c;while(scanf("%d%d",&n,&m)&&n+m){init();for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}dij(1);printf("%dn",d[n]);}return 0;
}

2.SPFA算法

SPFA很类似于BFS，都运用了队列,下面使用vector存边。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<queue>
#include<string>
using namespace std;
const int maxn=110;
const int inf=9999999;
int n,m,vis[maxn],d[maxn];
struct node
{int to,val;node(int a,int b):to(a),val(b){}
};
vector < node > v[maxn];
queue < int > q;
void spfa()
{memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)d[i]=inf;d[1]=0;q.push(1);vis[1]=1;//进队列标记为1，出队列标记为0while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(unsigned int i=0;i<v[now].size();i++){int next = v[now][i].to;int val = v[now][i].val;if(d[now]+val<d[next]){d[next]=d[now]+val;if(vis[next]==0){q.push(next);vis[next]=1;}}}}
}
int main()
{while(scanf("%d%d",&n,&m)&&n+m){int a,b,val;for(int i=1;i<=n;i++)v[i].clear();for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&val);v[a].push_back(node(b,val));v[b].push_back(node(a,val));}spfa();printf("%dn",d[n]);}return 0;
}

3.Floyd算法(多源最短路)

如果要用到 Floyd 算法建边方式基本都是邻接矩阵，因为时间复杂度为O(n^3)，所以说n通常都不会很大。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<queue>
#include<string>
using namespace std;
const int inf=999999999;
const int maxn = 1e2 + 5;
int n,m,vis[maxn],d[maxn];
int mp[maxn][maxn];
using namespace std;
void init()
{for(int i=1;i<=n;i++){mp[i][i]=0;for(int j=1;j<=n;j++){mp[i][j]=inf;}}
}
int main()
{while(scanf("%d%d",&n,&m)&&n+m){init();for(int i=1;i<=m;i++){int a,b,val;scanf("%d%d%d",&a,&b,&val);mp[a][b]=val;mp[b][a]=val;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);printf("%dn",mp[1][n]);}return 0;
}