一、负权形成环路的图为什么不能用弗洛伊德算法求任意两点之间的最短路径

负权形成环路的图,任意两点间可能没有最短路径。例如负权环C，点A,B是C上的点，A可以在C中转上任意圈后再沿C到B，这条路径权值可以任意小。而Floyd算法可以给出网络中任意两个节点之间的最短路径。

Floyd算法的基本思想

从任意节点A到任意节点B的最短路径不外乎2种可能：

所以，我们假设dist(AB)为节点A到节点B的最短路径的距离，对于每一个节点K，我们检查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，证明从A到K再到B的路径比A直接到B的路径短，我们便设置 dist(AB) = dist(AK) + dist(KB)，这样一来，当我们遍历完所有节点K，dist(AB)中记录的便是A到B的最短路径的距离。

Floyd算法与Dijkstra算法的不同

Floyd算法是求任意两点之间的距离，是多源最短路，而Dijkstra(迪杰斯特拉)算法是求一个顶点到其他所有顶点的最短路径，是单源最短路。

Floyd算法属于动态规划，我们在写核心代码时候就是相当于推dp状态方程，Dijkstra(迪杰斯特拉)算法属于贪心算法。

Dijkstra(迪杰斯特拉)算法时间复杂度一般是o(n2),Floyd算法时间复杂度是o(n3),Dijkstra(迪杰斯特拉)算法比Floyd算法块。

Floyd算法可以算带负权的，而Dijkstra(迪杰斯特拉)算法是不可以算带负权的。并且Floyd算法不能算负权回路。

延伸阅读：

二、最短路径问题（SPP）

最短路径问题（Shortestpath problem）是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

最短路径问题根据初始条件的不同，可分为五种情况：

1）最短路径问题：旨在寻找图中两点之间的最短路径；

2）确定起点的最短路径问题：即已知起点，求最短路径的问题；

3）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；

4）确定起点终点的最短路径问题，即已知起点和终点，求两点之间的最短路径；

5）：全局最短路径问题：求图中任意两点间的最短路径。也可以合并为一种情况——全局最短路径问题，只要求出全局最短路径，那其余四种情况也已经包含在内了。

而计算最短路径的常用算法有迪杰斯特拉算法、贝尔曼-福特算法、弗洛伊德算法等，下面小竞将为大家一一介绍其基本概念、优缺点、适用情况和案例分析。

迪杰斯特拉（Dijkstra）算法：用于解决从起点到其他各结点的最短路径，解决的是有向图中最短路径问题。其主要特点是以初始点为中心向外层层扩展，直到扩展到终点为止，但也有图中不能存在负权值的边的限制。

贝尔曼-福特(Bellman–Ford)算法：用于解决从起点到其他各节点的最短距离。与迪杰斯特拉算法不同的是，贝尔曼-福特算法可支持存在负权重的情况，即打破了图中不能存在负权值的边的限制，其边的权值可以为负数、实现简单，但也存在时间复杂度过高的缺点。可对原始算法进行若干优化，提高效率。贝尔曼-福特算法可用于解决以下问题：

1）从A出发是否存在到达各个节点的路径(有计算出值当然就可以到达)；

2）从A出发到达各个节点最短路径(时间最少、或者路径最少等)；

3）图中是否存在负环路（权重之和为负数）。

上一篇

计算机存储中符号占用字节空间大小的依据是什么?

下一篇

做ACM算法用什么开发工具?