Floyd-Warshall

Floyd-Warshall算法是一种用于寻找加权图中多源点之间最短路径的算法。它可以正确处理有向图或负权边的情况，但不能处理带有负权回路的图。该算法的时间复杂度为O(n^3)，其中n是图中顶点的数量。

以下是Floyd-Warshall算法的主要思想：
1. 以每个顶点为中间点，对所有的顶点间距离进行松弛。
2. 重复执行步骤1，直到所有的顶点都被当做中间点进行了一次松弛。

以下是一个使用Floyd-Warshall算法求解最短路径的Python代码示例：

# 初始化邻接矩阵
INF = float('inf')
graph = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
]

# 使用Floyd-Warshall算法求解最短路径
n = len(graph)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

# 输出最短路径
for i in range(n):
    for j in range(n):
        if graph[i][j] == INF:
            print("INF", end="\t")
        else:
            print(graph[i][j], end="\t")
    print()

输出结果为：

0	5	8	9	
INF	0	3	4	
INF	INF	0	1	
INF	INF	INF	0