（1）floyd
*时间复杂度O(n^3); *最简单最好记最好打的最短路算法； *可计算任意两点间的最短路；
*适合带负权的情况；
int dis[10010][10010]; int main() { int n,m,x,y,len; scanf("%d%d",&n,&m); memset(dis,0x3f,sizeof(dis)); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&len); dis[x][y]=len; } for (int k=1;k<=n;k++) // 中间点必须在最外层； for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } （2）dijkstra
*时间复杂度O(n^2); *稳定，计算一个点到其他所有点的最短路； *不能处理负权；
int d[10010],dis[10010][10010]; bool vis[10010]; int x,y,len,n,m; void dj(int s) { memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) d[i]=dis[s][i]; vis[s]=1; d[s]=0; for (int i=1;i<n;i++) { int mn=inf; int k=0; for (int j=1;j<=n;j++) if (!vis[j]&&d[j]<mn) mn=d[j],k=j; vis[k]=1; for (int j=1;j<=n;j++) if (!vis[j]) d[j]=min(d[j],d[k]+dis[k][j]); } } int main() { scanf("%d%d",&n,&m); memset(dis,0x3f,sizeof(dis)); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&len); dis[x][y]=len; } for (int i=1;i<=n;i++) dis[i][i]=0; scanf("%d%d",&x,&y); dj(x); printf("%d",d[y]); return 0; } （3）dijkstra的堆优化*时间复杂度O(n+mlogm); *用到stl中的优先队列 priority_queue；
#include<queue> int n,m,a,b,c,num=0,v[10001]={0},dis[10001]; bool vis[10001]; struct yts { int x,y,l,ne; }e[100010]; struct QQ { int x,len; }; struct cmp { bool operator()(QQ a,QQ b) { return a.len>b.len; } }; priority_queue<QQ,vector<QQ>,cmp>q; void put(int x,int y,int l) { num++; e[num].x=x; e[num].y=y; e[num].l=l; e[num].ne=v[x]; v[x]=num; } void dj() { for (int i=1;i<=n;i++) dis[i]=inf; dis[1]=0; q.push((QQ){1,0}); int x,y; while (!q.empty()) { x=q.top().x; q.pop(); if (vis[x]) continue; vis[x]=1; for (int i=v[x];i;i=e[i].ne) { y=e[i].y; if (dis[y]>dis[x]+e[i].l) { dis[y]=dis[x]+e[i].l; q.push((QQ){y,dis[y]}); } } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); put(a,b,c); } dj(); for (int i=1;i<=n;i++) printf("%d%c",dis[i],' '); return 0; } （4）spfa *时间复杂度玄学，不稳定； *可以处理带负权的最短路； *不能处理带负环的最短路； *bellmen-fald的优化； *计算一个点到其他所有点的最短路；int n,m,x,y,num,len; int dis[10010],v[10010]; bool vis[10010]; queue<int>q; struct mc { int x,y,len,ne; }e[100010]; void put(int x,int y,int len) { num++; e[num].x=x; e[num].y=y; e[num].len=len; e[num].ne=v[x]; v[x]=num; } void spfa(int s) { memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); q.push(s); dis[s]=0; vis[s]=1; while (!q.empty()) { int x=q.front(); vis[x]=1; q.pop(); for (int i=v[x];i;i=e[i].ne) { int y=e[i].y; if(dis[x]+e[i].len<dis[y]) { dis[y]=dis[x]+e[i].len; if(!vis[y]) { vis[y]=1; q.push(y); } } } vis[x]=0; } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&len); put(x,y,len); } scanf("%d%d",&x,&y); spfa(x); printf("%d",dis[y]); return 0; }
