floyd算法求最短路径python

Floyd算法是一种动态规划算法，用于求解图中所有节点之间的最短路径。它的时间复杂度为O(n^3)，适用于较小的图。

在Python中，可以使用二维数组来表示图，其中数组元素a[i][j]表示节点i到节点j的距离。如果节点i和节点j之间没有边相连，则a[i][j]的值为无穷大。

以下是Floyd算法的Python实现：

def floyd(graph):
    n = len(graph)
    dist = [[] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            dist[i][j] = graph[i][j]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

其中，graph是一个二维数组，表示图的邻接矩阵。函数返回一个二维数组dist，其中dist[i][j]表示节点i到节点j的最短路径长度。

例如，对于下面这个图：

--1--2
|  |  |
3--4--5

其邻接矩阵为：

graph = [
    [, 1, 1, float('inf'), float('inf'), float('inf')],
    [1, , 1, 1, float('inf'), float('inf')],
    [1, 1, , float('inf'), 1, 1],
    [float('inf'), 1, float('inf'), , 1, float('inf')],
    [float('inf'), float('inf'), 1, 1, , 1],
    [float('inf'), float('inf'), 1, float('inf'), 1, ]
]

调用floyd函数：

dist = floyd(graph)

得到的dist为：

[
    [, 1, 1, 2, 2, 2],
    [1, , 1, 1, 2, 2],
    [1, 1, , 2, 1, 1],
    [2, 1, 2, , 1, 3],
    [2, 2, 1, 1, , 1],
    [2, 2, 1, 3, 1, ]
]

其中，dist[i][j]表示节点i到节点j的最短路径长度。例如，dist[][5]表示节点到节点5的最短路径长度为2。