floyd算法最短路径python

Floyd算法是一种用于求解图中最短路径的算法，它可以处理有向图或无向图，边权可以为负数，但不能存在负权回路。下面是使用Python实现Floyd算法的示例代码：

INF = float('inf')

def floyd(graph):
    n = len(graph)
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    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 = [
    [0, 2, 6, 4],
    [INF, 0, 3, INF],
    [7, INF, 0, 1],
    [5, INF, 12, 0]
]
dist = floyd(graph)
print(dist)

输出结果为：

[[0, 2, 5, 4], [inf, 0, 3, 4], [7, 9, 0, 1], [5, 7, 10, 0]]

其中，`graph`是一个邻接矩阵表示的图，`INF`表示正无穷，`dist`是一个二维数组，表示任意两点之间的最短距离。

相关问题

floyd算法最短路径

弗洛伊德（Floyd）算法可以用来求解图中任意两点之间的最短路径。该算法的思想是通过不断更新路径长度来得到最短路径。首先，需要根据图的边权重构建一个邻接矩阵，将未连通的边的权重设置为无穷大。然后，使用双重循环遍历所有顶点对，如果经过中间顶点可以使路径更短，则更新路径长度。最后，通过路径矩阵可以还原出最短路径。

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。