贝尔曼福特（Bellman-Ford）算法：
大致流程：
将每一条边的信息（from，to，val）都记录到数组里
使用一个dis数组记录各点到源点的距离，初始化为INF。
然后不断循环进行松弛操作：遍历所有边，假如出现
dis[a.from]!=INF&&dis[a.to]<dis[a.from]+a.val就执行转移。
只要有任何一次循环没有发生松弛操作，循环退出，算法结束。
特点：
可以解决负边问题，但是无法解决负环问题，效率较慢，时间复杂度O(NM)
const int INF=0x3f3f3f3; bool V[MAX]; int dis[MAX]; struct edge{ int from,to,val; }; edge e[MAX]; void short(){ for(int i=1;i<=N;i++) dis[i]=INF; while(1){ int ok=0; //表示改过没有 for(int i=1;i<=N;i++){ edge a=e[i]; if(dis[a.from]!=INF&&dis[a.to]<dis[a.from]+a.val){ dis[a.to]=dis[a.from]+a.val; ok=1; } } if(ok==0) break; } }
迪杰斯特拉（Dijkstra）算法：
大致流程：
使用vector或者数组来记录不同的边（取决于稀疏图和稠密图）
稀疏图和稠密图(给个大概的划分）：用n 表示图中顶点数目，用e 表示图中边或弧的数目 稀疏图： e < nlogn ----使用vector好点 稠密图 e >nlogn ----使用数组好点
然后使用dis数组记录点到源点的距离，定义一个优先队列，优先队列里存放的是一个pair（dis，i），以dis排序。
每一次从队列中取出一个点，遍历所有与它有关的边，如果符合dp[e.to]>dp[point]+e.val，那么就将更新dis，点加进队列里面。
直到队列里面没有元素，结束。
while(!Q.empty()){ P ori=Q.top(); Q.pop(); int dis=ori.first; int point=ori.second; if(dp[point]<dis) continue; for(int i=0;i<E[point].size();i++){ edge e = E[point][i]; if(dp[e.to]>dp[point]+e.val){ dp[e.to]=dp[point]+e.val; Q.push(P(dp[e.to],e.to)); } } } if(dp[end]==INF){ cout<<-1<<endl; } else cout<<dp[end]<<endl; }特点：比贝尔曼快，我这个版本是堆优化版的，时间复杂度O（nlogn)，不能解决负边问题。
为什么不能解决负边问题呢，引用https://blog.csdn.net/lixing333/article/details/41324313博客的一段话：
不过，Dijkstra算法有一个限制，就是它只适用于边长不为负的图。如果一张图里有负数长的边长，那么Dijkstra算法就不适用了。这时候就需要另外的算法了。
为什么不适用呢？其实很容易就可以找到反例。假设一张加权图，有的边长为负数。假设边长最小为-10，我们把所有的边长都加上10，就这就可以得到一张无负值加权图。此时用Dijkstra算法算出一个从节点s到节点t的最短路径L，L共包括n条边，总长为t；那么对于原图，每条边都要减去10，所以原图中L的长度是t-10*n。这是Diskstra算法算出的结果。
那么问题来了：对于加上10之后的图，假设还有一个从s到t的路径M，长度为t1，它共包括n1条边，比L包含的边长多，那么还原回来之后，每条边需要减去10，那么M的总长就是t1-10*n1。那么，是不是M的总长一定比L的总长更长一些呢？不一定。假如n1>n，也就是说M的边数比L的边数更多，那么M减去的要比L减去的更多，那么t1-10*n1<t-10*n是可能的。此时Dijkstra算法是不成立的。 --------------------- 作者：彳亍而行的博客 来源： 原文：https://blog.csdn.net/lixing333/article/details/41324313 版权声明：本文为博主原创文章，转载请附上博文链接！
弗洛伊德（Flody）算法：
这个算法是最有辨识度的，forforfor
特点：效率奇低O(n^3)，但是可以求任意两点的最短路径，也可以解决负边问题（滑稽）
for(int k=0;k<V;i++){ for(int i=1;i<=n;i++){ for(int j=1;i<=n;j++){ if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; } } }SPFA算法：
其实SPFA和Bellmanford算法最坏时间复杂度一样，因此假如别人诚心想卡的话也会一起被卡，对于非负边的图还是优先迪杰斯特拉算法。
一般情况下它还是会比贝尔曼福特算法快一些，它使用了一个数列，使得减少了很多不必要的遍历。
while(!Q.empty()){ int point=Q.front(); flag[point]=0; //这里flag要变0 Q.pop(); for(int i=0;i<V[point].size();i++){ edge e=V[point][i]; if(dp[point]+e.val<dp[e.to]){ dp[e.to]=dp[point]+e.val; if(!flag[e.to]){ Q.push(e.to); flag[e.to]=true; cnt[point]++; } if(cnt[point]>=N) { //同一个点遍历超过N次即视为负环 ok=0; return ; } } } } }
