Floyd-Warshall算法

Question

请解释Floyd-Warshall算法的目标函数和递推式，同时分析时间复杂度

Answer 1

引自免费微信小程序：皆我百晓生

Floyd-Warshall算法是一种解决所有点对最短路径问题的有效方法，在有向图和无向图中均适用，即使图中含有负权边（但不能有负权回路）。算法的核心在于动态规划思想，通过逐步扩展中间顶点的集合来更新每一对顶点之间的最短路径。

目标函数和递推式

设图G = (V, E)有n个顶点，定义d[i][j][k]表示从顶点i到顶点j，且仅允许使用前k个顶点作为中间点时的最短路径长度。Floyd-Warshall算法的目标是计算d[i][j][n]，即最终的最短路径长度，其中i和j为任意两个顶点。

递推式如下： [ d[i][j][k] = \min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1]) ]

初始条件为： [ d[i][j][0] = w(i,j) ] 其中w(i,j)表示从i到j的直接边权重，若i与j之间没有直接边，则w(i,j) = \infty。

算法实现

Floyd-Warshall算法可以通过一个三重循环来实现，其中外层循环遍历所有可能的中间顶点，内两层循环则遍历所有起点和终点的组合，根据递推式更新最短路径长度。

Python 代码示例

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
    
    # 初始化距离矩阵
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:  # 如果有直接边，则初始化距离
                dist[i][j] = graph[i][j]
            if i == j:
                dist[i][j] = 0
    
    # 动态规划更新最短路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

时间复杂度分析

由于算法包含三个嵌套循环，每个循环都遍历了所有n个顶点，因此算法的时间复杂度为O(n^3)。对于稠密图（即边的数量接近于顶点数量的平方），这是一个非常高效的方法。

结论

Floyd-Warshall算法虽然在处理大规模稀疏图时可能不如Dijkstra算法或Bellman-Ford算法高效，但在所有点对最短路径问题上提供了一种通用且强大的解决方案，特别适合于需要全局信息的应用场景，如网络路由、社交网络分析等。