0%

最短路径

单源最短路径

单源最短路径问题是从源结点到其它结点的最短路径问题。

一般解决方案是 Bellman-Ford 算法,其允许负值权重的边。当存在负值环路时,算法返回不存在问题的解,否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。

还有著名的 Dijkstra 算法,其要求所有边的权重都为非负。其利用了贪心算法的思想,每次都选择最短路径。

全点对最短路径

全点对最短路径问题是从任一结点到其余结点的最短路径的问题。

如果不存在负值权重的边,可以用 Dijkstra 算法对每个结点进行操作。

还有一种利用动态规划思想的 Floyd-Warshall 算法,其要求可以存在负值权重的边,但不可以存在负值回路。