Floyd算法详解（Python语言实现最短路径算法）

Floyd算法的步骤

1. 初始化一个距离矩阵 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的直接距离。如果 i 和 j 之间没有直接边，则设为无穷大（通常用 float('inf') 表示）；若 i == j，则 dist[i][j] = 0。
2. 对于每一个可能的中间顶点 k（从 0 到 n-1），检查是否通过 k 可以缩短 i 到 j 的路径：如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j]。
3. 重复上述过程，直到所有中间节点都被考虑过。

Python实现Floyd算法

下面是一个完整的、易于理解的Python实现Floyd算法的代码示例：

def floyd_warshall(graph):    """    使用Floyd-Warshall算法计算所有顶点对之间的最短路径    :param graph: 邻接矩阵，graph[i][j] 表示从i到j的边权重    :return: 最短路径距离矩阵    """    # 获取顶点数量    n = len(graph)        # 初始化距离矩阵（复制原图）    dist = [[graph[i][j] 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):        # 终点                # 如果经过k能缩短i到j的距离，则更新                if dist[i][k] + dist[k][j] < dist[i][j]:                    dist[i][j] = dist[i][k] + dist[k][j]        return dist# 示例：定义一个带权图（邻接矩阵）# 使用 float('inf') 表示无直接连接INF = float('inf')graph = [    [0,   3,   INF, 7],    [8,   0,   2,   INF],    [5,   INF, 0,   1],    [2,   INF, INF, 0]]# 调用Floyd算法result = floyd_warshall(graph)# 打印结果print("所有顶点对之间的最短距离：")for row in result:    print(["{:>5}".format(str(x) if x != INF else "INF") for x in row])

代码解析

• 邻接矩阵：我们用二维列表表示图，其中 graph[i][j] 是从顶点 i 到 j 的边权重。
• INF：代表无穷大，即两个顶点之间没有直接路径。
• 三层循环：最外层是中间节点 k，内两层遍历所有起点 i 和终点 j。
• 动态更新：只要发现更短路径（i→k→j 比 i→j 短），就立即更新距离矩阵。

应用场景

Floyd算法广泛应用于网络路由、交通规划、社交网络分析等领域。虽然它的复杂度较高，但由于其简洁性和能一次性求出所有点对最短路径的特点，在小规模图或需要全源最短路径时非常实用。

总结

通过本教程，你已经掌握了如何用Python语言实现Floyd算法来解决最短路径算法问题。Floyd算法作为经典的图论算法之一，不仅逻辑清晰，而且代码简洁。希望你能动手尝试，加深理解！

关键词回顾：Floyd算法、Python实现Floyd算法、最短路径算法、图论算法