Bellman-Ford算法

适用条件&范围

1. 单源最短路径(从源点s到其它所有顶点v);
2. 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3. 边权可正可负(如有负权回路输出错误提示);
4. 差分约束系统;

算法描述

1. 对每条边进行|V|-1次Relax操作;
2. 如果存在(u,v)∈E使得dis[u]+w<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。

For i:=1 to |V|-1 do //v为顶点数
For 每条边(u,v)∈E do  //对每条边进行遍历
  Relax(u,v,w);
For每条边(u,v)∈E do
  If dis[u]+w<dis[v] Then Exit(False)

时空复杂度

算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。

改进和优化

SPFA

参考代码

PASCAL

Matlab

引用&参考

• 菜鱼《图论总结》

链接

[编辑]

图论及图论算法

图 - 有向图 - 无向图 - 连通图 - 强连通图 - 完全图 - 稀疏图 - 零图 - 树 - 网络

基本遍历算法：宽度优先搜索 - 深度优先搜索 - A* - 并查集求连通分支 - Flood Fill

最短路：Dijkstra - Bellman-Ford（SPFA） - Floyd-Warshall - Johnson算法

最小生成树：Prim - Kruskal

强连通分支：Kosaraju - Gabow - Tarjan

网络流：增广路法（Ford-Fulkerson，Edmonds-Karp，Dinic） - 预流推进 - Relabel-to-front

图匹配 - 二分图匹配：匈牙利算法 - Kuhn-Munkres - Edmonds' Blossom-Contraction