8. Shortest path in graph with negative edges

8. Shortest path in graph with negative edges

Shortest path algorithm

BFS: single source shortest path in graph with no edge weight

Dijkstra: single source shortest path in graph with non-negative edge weight

Dynamic programming/Topological sort: single source shortest path in DAGs

Bellman ford:  single source shortest path in graph with no negative cycle

为什么Dijkstra算法不适用边长为负数的情况(link)

Negative edge: an edge e is negative if w(e) < 0

Negative cycle: a cycle \( C=c_{1},c_{2}…c_{k}\) is negative if \( \sum_{i=1}^K w(e_{i}) < 0\)

Bellman ford algorithm

Bellman – ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成

对于许多图而言,任意最短路径的边数实际上都小于\(|V|-1\),因此有必要增加一个额外的检查:在没有任何更新发生时,立即终止算法。