Bellman-Ford算法
Dijkstra算法无法判断含负权边的图的最短路。
如果遇到负权,在没有负权回路存在时,即便有负权的边,也可以采用Bellman-Ford算法正确求出最短路径。
PS:负权回路的含义是,回路的权值和为负。
算法描述
1.初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
2.迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)
3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在 d[v]中。
伪代码:
For i= to |G.V|-
For each edge(u,v)属于G.E
RELAX(u,v,w)
For each edge(u,v)属于G.E
If (v.d>u.d+w(u,v)
Return FALSE;
Return TRUE;
时间复杂度:O(VE) 即顶点数*边数