什么是Floyd算法？

Floyd算法（Floyd-Warshall算法）是一种用于寻找给定加权图中所有顶点对之间最短路径的算法。该算法名称取自创始人罗伯特·弗洛伊德（Robert Floyd）和斯蒂芬·沃舍尔（Stephen Warshall）。

Floyd算法的时间复杂度为 O(n³)，其中 n 是图中顶点的数量。虽然时间复杂度较高，但其优势在于可以一次性计算出所有顶点对之间的最短路径。

Floyd算法步骤详解

算法伪代码：

function floydWarshall(graph):
    n = number of vertices in graph
    dist = matrix of size n*n initialized with graph values
    
    for k from 0 to n-1:
        for i from 0 to n-1:
            for j from 0 to n-1:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Python实现Floyd算法

下面是Floyd算法的完整Python实现，包括路径重建功能：

INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    
    # 初始化距离矩阵和路径矩阵
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    next_node = [[j if graph[i][j] != INF else -1 for j in range(n)] for i in range(n)]
    
    # Floyd算法核心
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]
    
    return dist, next_node

def reconstruct_path(start, end, next_node):
    if next_node[start][end] == -1:
        return []
    
    path = [start]
    while start != end:
        start = next_node[start][end]
        path.append(start)
    
    return path

# 示例图
graph = [
    [0, 3, INF, 7],
    [8, 0, 2, INF],
    [5, INF, 0, 1],
    [2, INF, INF, 0]
]

# 执行算法
distances, next_nodes = floyd_warshall(graph)

# 输出结果
print("距离矩阵:")
for row in distances:
    print(row)

start, end = 0, 3
path = reconstruct_path(start, end, next_nodes)
print(f"\n从顶点 {start} 到顶点 {end} 的最短路径: {path}")
print(f"最短距离: {distances[start][end]}")

算法可视化

上图展示了示例代码中的图结构，顶点0到顶点3的最短路径为0→1→2→3，距离为6

应用场景

• 交通网络规划（城市间最短路径）
• 计算机网络路由优化
• 社交网络中的关系距离计算
• 物流配送路径优化
• 游戏开发中的AI路径寻找
• 电路设计中的最短布线

优缺点分析