floyd-warshall算法详解

一、floyd-warshall算法

floyd-warshall算法是一种用于解决所有节点对之间的最短路径问题的算法。该算法基于动态规划的思想，它采用的是一种分治的策略，在不断迭代中使得问题规模逐渐减小。该算法的时间复杂度为O(n^3)。

floyd-warshall算法是以“中间节点”为分界线，通过将中间节点逐渐加入，从而得到所有节点对之间的最短路径。具体实现时，需要在二维矩阵中设置三维数组，第三维表示中间节点，依次遍历每个中间节点，然后计算出以该节点为中间节点的最短距离。

二、floyd-warshall算法空间复杂度

考虑到实际应用中图的节点数很大，如果使用邻接矩阵进行全对全最短路径计算，空间开销将会非常大。具体而言，对于一个大小为n的图，邻接矩阵占用的空间复杂度为O(n^2)。由此， floyd-warshall算法的空间复杂度也将达到O(n^3)。但是，可以通过优化空间的方法进行改善，具体而言，可以设置一个n*n的矩阵，其中的每个元素表示从i节点到j节点的最短路径，每次迭代只需要更新矩阵的一部分，这样可以将空间复杂度降低到O(n^2)。

三、floyd-warshall怎么读

floyd-warshall算法是由两位科学家Robert Floyd 和 Stephen Warshall 合作提出的算法，因此，读作“floyd-沃舍尔算法”。

四、floyd-warshall算法图解

下图是一个采用floyd-warshall算法求取两个节点之间最短路径的示意图。其中，红色数字表示每个节点的编号，黑色数字表示两个节点之间的距离。

<img src="fw.png" alt="floyd-warshall算法图解">

在该图中，我们可以看到，如果要求节点1到8之间的最短路径，那么我们可以通过不断迭代，分别将2、3、5、6、7加入，最终得到节点1到8之间的最短距离为14。

五、floyd-warshall三重循环

下面是floyd-warshall算法的主要实现函数：

def floydWarshall(graph):    
    dist = list(map(lambda i : list(map(lambda j : j , i)) , graph))    
    for k in range(len(graph)):         
        for i in range(len(graph)):             
            for j in range(len(graph)):                 
                dist[i][j] = min(dist[i][j] , dist[i][k]+ dist[k][j])    
    return dist

该函数使用了三重循环，其中第一重循环遍历中间节点，第二重循环遍历起始节点，第三重循环遍历结束节点，具体实现时，每次迭代更新dist[i][j]的值，使之成为经过中间节点k的最短路径。

六、floyd-warshall算法中的k

floyd-warshall算法中的k表示中间节点，当我们遍历每个k时，相当于将其当作中转站，来计算两个节点之间的距离。在具体实现时，我们可以使用三重循环来遍历每个节点对之间的距离，并不断更新dist[i][j]的值。

七、floyd-warshall算法时间复杂度

floyd-warshall算法的时间复杂度为O(n^3)。这是因为，在计算最短路径时，需要遍历所有的中间节点，而对于每个中间节点，都需要遍历一遍所有的节点对，因此总的遍历次数为n*n*n。

八、floyd-warshall算法思想

floyd-warshall算法的思想是“分治”，即将每个中间节点当作中转站，来计算两个节点之间的距离。具体而言，我们可以使用一个二维矩阵来存储每两个节点之间的距离，然后通过逐步加入中间节点，来求取所有节点对之间的距离。

九、floyd-warshall算法贪心

floyd-warshall算法并不是一种贪心算法。它是一种基于动态规划的算法，它采用的是一种分治的策略，在不断迭代中使得问题规模逐渐减小。

十、floyd-warshall算法求负环

floyd-warshall算法也可以用来判断图中是否存在负环。具体而言，在floyd-warshall算法求得所有节点之间最短路径的过程中，如果某一次迭代中dist[i][i]出现了负数，那么就说明图中存在负环。

下面是代码示例：

def floydWarshall(graph):    
    dist = list(map(lambda i : list(map(lambda j : j , i)) , graph))    
    for k in range(len(graph)):         
        for i in range(len(graph)):             
            for j in range(len(graph)):                 
                dist[i][j] = min(dist[i][j] , dist[i][k]+ dist[k][j])    
        if dist[k][k] < 0:            
            return "存在负环"    
    return dist

上述代码中，如果在某一次迭代中dist[k][k]出现了负数，那么该函数就会返回“存在负环”。

原创文章，作者：WURZ，如若转载，请注明出处：https://www.506064.com/n/133652.html