常用四大最短路算法：
Dijkstra: 平凡实现O（V^2），使用数据结构堆优化O（ElogV），不适用于负权 半优推
Bellman-Ford: O(（V*E）适用负权
SPFA: O（kE (k一般<=2)） 适用负权 优推
Floyd-Warshall: O（V^3）适用负权
SPFA操作：
（1）初始化： d数组全部赋值为INF（无穷大），d[s]=0；prev数组全部赋值为-1，表示还没有知道前驱；
ps：在整个算法中有顶点入队标记vis数组，有顶点出队了消除那个标记；
（2）队列+松弛操作：读取队头顶点u，并将队头顶点u出队（出队消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（入队标记），如果已经在队列中了，那么就不用入队，以此循环，直到队空为止就完成了单源最短路的求解；
下面是几种最短路的实现代码，由于存储数据的数据结构的不同，遍历操作可能略有不同，邻接表的几种实现参见点击打开链接；
Bellman-Ford：
struct edge { int from; int to; int cost; }es[E]; int d[V]; void Bellman-Ford(int s) { for(int i=1;i<=V;i++) d[i]=INF; d[s]=0; while(true) { bool update=false; for(int i=1;i<=E;i++) if(d[es[i].from]!=INF&&d[es[i].to]>d[es[i].from]+es[i].cost) { d[es[i].to]=d[es[i].from]+es[i].cost; update=true; } if(!update) break; } } int main() { /*...*/ for(int i=1;i<=E;i++) { scanf("%d%d%d",&es[i].from,&es[i].to,&es[i].cost); } Bellman-Ford(1); /*...*/ return 0; }
Dijkstra:（一般实现O（V^2））
int cost[max_V][max_V];//不存在时INF int d[max_V]; bool used[max_V]; int V; //从s出发的各个顶点的最短距离 void dijkstra(int s) { fill(d,d+V,INF); fill(used,used+V,false); fill(prev,prev+V,-1); d[s]=0; while(true) { int v=-1; //从尚未使用过的顶点中选择一个距离最小的顶点 for(int u=0;u<V;u++) { if(!used[u]&&(v<0||d[u]<d[v])) v=u; } if(v==-1) break;//说明已更新完毕 used[v]=1;//加入已经求得最短路径的集合中 for(int u=0;u<V;u++) if(d[u]>d[v]+cost[v][u]) { d[u]=d[v]+cost[v][u]; prev[u]=v; } /*若不求路径 for(int u=0;u<V;u++) d[u]=min(d[u],d[v]+cost[v][u]); */ } } //到顶点t的最短路 vector<int> Path(int t) { vector<int> path; for(;t!=-1;t=prev[t]) path.push_back(t); //翻转 reserve(path.begin(),path.end()); return path; }SPFA_bfs:（优推） int spfa_bfs(int s) { queue<int> q; memset(d,0x3f,sizeof(d)); d[s]=0; memset(cnt,0,sizeof(cnt)); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; cnt[s]=1;//顶点入队vis要做标记，另外要统计顶点的入队次数 while(!q.empty()) { int x; u=q.front(); q.pop(); vis[u]=0;//队头元素出队，并且消除标记 for(int i=head[u];~i;i=edge[i].next)//采用链式前向星的遍历 { int v=edge[i].to; if( d[u]+edge[i].cost<d[v]) { d[v]=d[u]+edge[i].cost; if(!vis[v]) { vis[v]=1; //标记 cnt[v]++; //统计次数 q.push(v); //入队 if(cnt[v]>V) //存在一点入队次数大于总顶点数，说明有负环 return 0; } } } } return 1; }
Floyd:（多源点最短路）
/*核心：dp思想*/ int d[max_v][max_v];//边的权值，不存在设为INF，不过d[i][i]=0 void floyd() { for(int k=0;k<v;k++) for(int i=0;i<V;i++) for(int j=0;j<V;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); }