使用示例

Floyd 算法是一种用于求图中的所有顶点对之间的最短路径的算法。它特别适用于带权图中存在负权边的情况。以下是 Floyd 算法的中文解释：

Floyd 算法简介

Floyd 算法通过不断更新邻接矩阵来找到所有顶点对之间的最短路径。其基本思想是：对于每对顶点 (i) 和 (j)，尝试找到一个中间顶点 (k)，如果通过 (k) 的路径比当前已知的路径更短，则更新 (i) 到 (j) 的最短路径。

算法步骤

1. 初始化一个邻接矩阵 (dist)，其元素 (dist[i][j]) 表示顶点 (i) 到顶点 (j) 的最短距离。如果 (i) 和 (j) 之间没有路径，则 (dist[i][j]) 的值为无穷大。
2. 遍历所有顶点 (k)，更新邻接矩阵。对于每对顶点 (i) 和 (j)，检查 (dist[i][k] + dist[k][j]) 是否小于 (dist[i][j])。如果是，则更新 (dist[i][j]) 为 (dist[i][k] + dist[k][j])。
3. 重复步骤 2，直到遍历所有可能的中间顶点 (k)。

代码示例

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            else:
                dist[i][j] = graph[i][j]
    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]
    return dist


graph = [
    [0, 3, float('inf'), 7],
    [8, 0, 2, float('inf')],
    [5, float('inf'), 0, 1],
    [2, float('inf'), float('inf'), 0]
]
result = floyd_warshall(graph)
for row in result:
    print(row)

相关阅读

如果您想了解更多关于图论的知识，可以访问图论教程。

Floyd 算法图解