用代码表示Warshall算法

Warshall算法，也称为Floyd-Warshall算法，用于求解有向图或无向图中的所有对之间的最短路径。这是一个动态规划算法，通过迭代更新距离矩阵来找到从任意节点到其他所有节点的最短路径。

下面是使用Python实现的Warshall算法：

def floyd_warshall(graph):
    # 图形是一个邻接矩阵，其中graph[i][j]表示节点i到节点j的距离（默认为无穷大）
    num_nodes = len(graph)
    
    # 初始化一个与原始图相同大小的矩阵，用来存储最短路径
    shortest_paths = [[graph[i][j] for j in range(num_nodes)] for i in range(num_nodes)]
    
    # 遍历所有的节点
    for k in range(num_nodes):
        # 检查是否存在中间节点k使得从i到j的路径更短
        for i in range(num_nodes):
            for j in range(num_nodes):
                if i != j and shortest_paths[i][k] + graph[k][j] < shortest_paths[i][j]:
                    shortest_paths[i][j] = shortest_paths[i][k] + graph[k][j]
                    
    return shortest_paths

# 示例：
graph = [
    [0, 1, 5, float('inf')],
    [float('inf'), 0, 3, 1],
    [float('inf'), float('inf'), 0, 6],
    [float('inf'), float('inf'), float('inf'), 0]
]

shortest_distances = floyd_warshall(graph)

for i, row in enumerate(shortest_distances):
    print(f"Shortest distances from node {i}: {row}")

在这个例子中，`graph`是一个二维列表，其中`graph[i][j]`表示从节点`i`到节点`j`的距离。`floyd_warshall`函数返回一个新的矩阵，其中包含了从每个节点到其他所有节点的最短路径。