图论
最短路
dijkstra
时间复杂度：N^2
堆优化版的就是优化找最小距离点 时间复杂度：M*logN
特点：不允许存在负权边
算法原理：用最短距离去更新n个点的距离（实际有效更新的只有连边）
bellman-ford
时间复杂度：K*M （K是步数，M是边数）
能处理负权边，可以处理负环，可以判断回路，可以解决最多k步问题
算法原理：走k步，每次松弛所有点
细节：1，松弛操作一定要用上一次最短距离上的点更新当前点距离，为了避免串联计算（k不合法）
2，负权边可能会更新n的最短距离，所以当k步无法到达点n时，d[n]可能是一个小于0x3f3f3f3f的数
spfa
时间复杂度：最坏 M*N 一般情况下：M*logN
能处理负权边（不允许存在负环），判断回路（比bellman-ford更优，实际上就是bellman-ford的优化版本，bellman无脑更新n个点）
算法原理：维护一个队列，这个队列存储拥有合法最短路径的点，每次更新这个点的所有连边
Floyd
不能有负权回路，可以处理两点间的最短路问题
由于f[k]都是由f[k-1]推得，可以优化成二维 ```f[i,j] = f[i,k] + f[k,j]```
本文作者：xiaolipro
本文链接：https://www.cnblogs.com/xiaolipro/p/14587214.html
版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。
标签：图论,复杂度,更新,ford,bellman,负权 From： https://www.cnblogs.com/sexintercourse/p/16897929.html