1. Floyd
基于动态规划
复杂度O(n^3)
找到任意两点之间的最短路径
放松通过每个点的所有其他路径
递归公式map[i][j]=min(map[i][j],map[i][k]+map[k][j])
关键代码
for(int k=1; k=n; k++)
for(int i=1; i=n; i++)
for(int j=1; j=n; j++)
地图[i][j]=min(地图[i][j], 地图[i][k] + 地图[k][j]);
2. Dijkstra
单源最短路径
基于贪婪（当路径值没有负权重时）
复杂度O(N^2) (邻接矩阵) 邻接矩阵
复杂度O((M+N)logN) （邻接表） 邻接表
当图中路径很少（m n^2）（稀疏图）时，最好使用邻接表
在dis[]中寻找最小值时，如果使用C++ STL中的优先级队列priority_queue，可以对常量进行优化。
本文主要研究基于C语言的最短路径算法，不占用太多篇幅实现二叉堆排序。
想法： 找到从A 点到所有其他点的最短路径。重复下面的步骤：找到距离A最近的B点，通过B点放松其他点（A点和B点之间的当前距离一定是最短的，因为无法通过其他点放松）（无负权重）。
邻接表
邻接表的存储与链表类似，这里是通过结构体来实现的。假设路径数为m1000，节点数为n300。
typedef 结构节点{
int u、v、w； //使用该结构体来存储读取路径
}节点； //u 起点v 终点w 路径权重
节点道路[1000];再定义两个数组来模拟链表
first[]的键名代表节点，键值代表路径号。
next[]的键名代表路径号，键值代表路径号。
它们通常被定义为初始值为0 的全局数组。
int first[300];//first[u]存储从节点u开始的第一条路径（读取时反向存储）
//所以数组空间应该大于等于节点数n
int next[1000];//next[i]存储路径i的下一条路径。这两条路径的起点相同
//所以数组空间应该大于等于边数m。读取路径时如何存储
cin 路[i].u 路[i].v 路[i].w; //读取第i条路径的起点、终点、权重
下一个[i]=第一个[路[i].u];
第一[路[i].u]=i;这是反向存储，最后一个读边沿被视为第一个，在first[]中。
邻接表存储有点复杂。让我尝试解释一下。
读取第i条边时的处理方法：
first[road[i].u] 存储从节点road[i].u 开始的上一条路径的路径号（可以记为i"）（如果现在读取的边以开头，则该节点是第一个起点路径，所以由于该数组是全局数组，所以first[road[i].u]的值为0，即i"==0）。现在将这条路径的编号赋给next[i]，表示路径i的下一条路径是i"，然后将i赋给first[road[i].u]。
邻接表的遍历
当要遍历从节点u开始的路径时，从first[u]开始，first[u]存储第一条边，然后不断获取next[边数]
int 头=第一个[u];
而（头！=0）
{
--- 在此边缘上执行操作---
头=下一个[头]；
}
Dijkstra(邻接表)核心代码
for(int i=1; inw + dis[tar])
dis[nv]=nw + dis[tar];
头=最后[头];
}
}
别的
休息；
}两种方法的核心代码比较相似，变量代表的含义也基本相同。
Dijkstra(邻接矩阵)核心代码
for(int i=1; imap[1][tar] + map[tar][j])
{
地图[1][j]=地图[1][tar] + 地图[tar][j];
}
}
}
}
3. Bellman-Ford
这个算法的思路和代码量都比较短。
可以看作是在牺牲Dijkstra部分复杂度的基础上能够判断和处理负权值以及判断负权值循环。
对于n个点、m条边的有向图，使用数组dis[]保存源点到每个点的最短距离。可以遍历边n-1次，当满足dis[v] dis[u] + w 时，对其进行松弛更新操作，重复n-1次即可得到答案。如果n-1次后还能继续更新，则可以判断图中出现了负权循环。
for(int i=1; idis[路[j].u] + 路[j].w)
{
检查=1；
dis[路[j].v]=dis[路[j].u] + 路[j].w;
}
}
如果（！检查）
休息；
}
4.SPFA
SPFA是在Bellman-Ford的基础上改进的
Bellman-Ford算法中，一方面不需要在每次循环中判断所有边的松弛情况，只需要对上一次松弛操作成功松弛的节点所延伸的边进行再次判断。
因此，我们添加一个队列，让成功放松的节点进入队列。 （类似于广搜的思想。不过，在n个节点的有向图中，对于任意节点i，即使该节点在n-1次操作之前松弛成功，也不一定是最短路径，可能因此，一个节点可能会多次进入队列，这与普通的BFS不同。
由于操作是针对每个节点的，因此在稀疏图中使用邻接表会更方便（这也是我们大多数人遇到的）。
SPFA代码(放上全文，一方面SPFA是应用得最多的单源最短路算法，另一方面之前写的时候遇到了点小bug,调试了好久， 长个记性)
#include#includeusing命名空间std;
整数n，m； //n=100，m=1000
typedef 结构节点{
int u、v、w；
}节点；
节点道路[1000];
intfirst_road[100],next_road[1000]; //邻接表
int 队列[1000]; //实现队列
整数倍[100]； //每个点进入队列的次数
布尔书[1000]；
整数dis[100]；
布尔标志； //判断负循环
int main()
{
cin n m;
for(int i=1; i=m; i++)
{
cin 路[i].u 路[i].v 路[i].w;
next_road[i]=first_road[road[i].u];
第一路[路[i].u]=i;
}
memset(dis,0x3f, sizeof(dis));
dis[1]=0;
int 头=0，尾=1；
队列[头]=1;
书[1]=1;
次[1]++；
while（头尾）
{
int now=队列[头]; //节点
int bian=first_road[现在]; //遍历节点的路径
同时（边）
{
if(dis[路[bian].v] dis[路[bian].u] + 路[bian].w)
{
dis[路[bian].v]=dis[路[bian].u] + 路[bian].w;
int next_node=路[bian].v;
if(书[下一个节点]==0)
{
if(times[下一个节点]=n)
{
标志=1；
休息；
}
书[下一个节点]=1;
队列[tail++]=next_node;
次[下一个节点]++；
}
}
bian=next_road[bian];
}
书[队列[头]]=0;
头++；
如果（标志）
休息；
}
如果（标志）
cout "存在负循环";
别的
for(int i=1; i=n; i++)
cout dis[i] " ";
计算结束；
返回0；
}
负环判断
Bellmam-Ford 和SPFA 算法都可以确定图的负循环。
对于Bellman-Ford：第n次松弛操作也能成功更新dis[]的值，则出现负循环。
对于SPFA：如果一个点进入队列n次，则存在负循环
结论
算法简述时间复杂度负权重和负权重循环Floyd 动态规划O(N^3) 可以处理负权重，但无法判断负权重循环Dijkstra 是贪心的，点处理呢O((M+N) logN) Bellman-Ford 边缘处理O(MN) 都无法处理负权重并判断负权重循环。 SPFA优化的BellmanO(MN)可以处理负权重并判断负权重循环
遇到的一些问题：
1. memset的原理
memset是为char[]设计的，处理字节，即memset(a,0xff,sizeof(a))，将a的每个字节变成ff。
当我们对int[]使用memset时，int 4个字节的每个字节都会是ff。
使用建议：
【图论中最短路算法性能对比：Floyd、Dijkstra、SPFA、Bellman算法详解】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
最近在学习图论算法啊，这几个最短路算法还是很有意思的。
有18位网友表示赞同！
Floyd算法是万能的吗？哪些情况下更适合使用它呢？
有8位网友表示赞同！
Dijkstra算法简单易懂，我记得学过一次貌似。但其他几种算法听起来比较复杂。
有9位网友表示赞同！
SPFA感觉在实际应用中会用到的机会多点吧。
有7位网友表示赞同！
Bellman-Ford算法处理负权边是不是挺厉害的？
有7位网友表示赞同！
我之前遇到过类似的最短路问题，不知道该用哪种算法比较好解决的问题。
有11位网友表示赞同！
这几个算法之间在时间复杂度和空间复杂度上有哪些区别呢？
有9位网友表示赞同！
图论真是个很强大的工具，可以用来解决很多现实问题啊。
有9位网友表示赞同！
想了解一下这些算法具体的实现方法。
有8位网友表示赞同！
有没有什么开源的代码例子可以参考一下？
有15位网友表示赞同！
我看了一下Floyd算法的时间复杂度是方程式的，怎么解释这个时间复杂度的吗？
有20位网友表示赞同！
其实在实际生活中，最短路问题会经常遇到吧。比如导航软件就用到了最短路径算法吧。
有15位网友表示赞同！
请问学习这几个算法有什么难点？
有16位网友表示赞同！
哪个算法的理解难度相对最低呢？
有7位网友表示赞同！
可以来个简要对比一下吗，哪种算法更适合解决哪些类型的最短路问题?
有19位网友表示赞同！
Floyd算法能处理多重边吗?
有13位网友表示赞同！
Dijkstra算法的数据结构是什么样的？
有18位网友表示赞同！
SPFA算法的稳定性如何呢？
有5位网友表示赞同！
Bellman-Ford算法对负权重的图处理是怎么实现的呢？
有16位网友表示赞同！
什么时候需要用到这几个最短路算法呢？有什么实际的应用场景吗？
有9位网友表示赞同！