使用百度文心一言生成弗洛伊德最短路径算法python源程序_弗洛伊德算法怎样写成代码

以下是使用Python实现弗洛伊德算法（Floyd算法）的示例代码，用于寻找图中的最短路径：

import random
def floyd(graph):
    n = len(graph)
    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != 0:
                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] != float('inf') and dist[k][j] != float('inf') and dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist
def generate_graph(n, m):
    graph = [[0] * m for i in range(n)]
    for i in range(n):
        for j in range(m):
            graph[i][j] = random.randint(1, 100)
    return graph

def run_floyd(n, m):
    graph = generate_graph(n, m)
    print(graph)
    print(floyd(graph))

if __name__ == "__main__":
    run_floyd(10, 50)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'
运行
运行

原图:[[97, 36, 41, 65, 35, 58, 81, 70, 63, 75, 36, 31, 66, 1, 21, 42, 79, 91, 10, 13, 81, 93, 89, 81, 87, 73, 46, 70, 51, 21, 18, 98, 76, 35, 54, 58, 93, 97, 7, 92, 59, 76, 87, 9, 68, 20, 49, 32, 64, 90], [84, 68, 91, 60, 11, 45, 85, 28, 34, 85, 6, 54, 4, 5, 56, 41, 4, 59, 89, 22, 61, 58, 23, 38, 16, 61, 60, 36, 37, 81, 4, 73, 25, 17, 23, 52, 1, 47, 26, 86, 65, 80, 47, 38, 34, 41, 93, 48, 41, 65], [31, 78, 7, 50, 67, 50, 63, 4, 66, 40, 74, 67, 52, 48, 82, 15, 99, 92, 91, 93, 17, 86, 94, 34, 2, 80, 92, 82, 71, 47, 96, 79, 38, 8, 8, 56, 83, 63, 67, 1, 9, 83, 11, 79, 4, 95, 72, 45, 49, 41], [20, 95, 34, 82, 13, 23, 52, 24, 35, 72, 62, 87, 52, 73, 7, 48, 29, 63, 15, 50, 32, 6, 54, 65, 17, 30, 99, 7, 96, 7, 67, 76, 34, 56, 45, 28, 54, 26, 39, 41, 53, 45, 85, 1, 52, 51, 64, 68, 51, 15], [76, 50, 54, 14, 16, 46, 76, 26, 94, 55, 69, 43, 24, 9, 68, 81, 25, 1, 51, 32, 47, 91, 31, 89, 44, 32, 49, 62, 7, 67, 63, 10, 49, 64, 3, 25, 57, 89, 42, 80, 86, 47, 85, 42, 78, 20, 52, 85, 48, 63], [94, 28, 3, 69, 77, 50, 2, 46, 49, 51, 59, 94, 6, 4, 75, 66, 18, 66, 51, 91, 37, 5, 25, 90, 81, 69, 58, 42, 43, 15, 5, 83, 17, 3, 96, 43, 39, 9, 46, 8, 77, 24, 29, 47, 14, 7, 31, 33, 5, 20], [67, 61, 9, 40, 65, 3, 35, 49, 100, 91, 32, 43, 53, 16, 11, 27, 88, 3, 24, 1, 32, 21, 3, 46, 29, 16, 7, 34, 64, 81, 65, 75, 84, 76, 85, 15, 100, 33, 75, 58, 90, 43, 89, 72, 98, 40, 98, 36, 31, 83], [82, 3, 30, 68, 65, 82, 98, 46, 3, 36, 63, 51, 29, 1, 23, 8, 7, 52, 48, 29, 61, 33, 24, 57, 17, 46, 86, 49, 3, 81, 18, 30, 43, 49, 83, 91, 26, 20, 12, 41, 66, 74, 10, 34, 36, 20, 30, 27, 16, 30], [93, 61, 21, 55, 35, 38, 52, 57, 53, 10, 49, 19, 30, 29, 40, 33, 45, 22, 30, 99, 45, 13, 17, 93, 40, 80, 91, 3, 61, 34, 7, 83, 83, 82, 34, 12, 38, 32, 85, 13, 81, 63, 66, 38, 41, 88, 61, 29, 47, 94], [82, 92, 62, 94, 1, 99, 82, 53, 2, 6, 95, 4, 51, 21, 55, 14, 20, 47, 83, 96, 59, 69, 62, 19, 67, 79, 95, 56, 73, 4, 69, 9, 88, 97, 14, 63, 95, 18, 89, 11, 87, 34, 19, 52, 10, 45, 38, 65, 97, 29]]
最短路径:[[0, 36, 41, 49, 35, 58, 60, 45, 48, 58], [45, 0, 48, 25, 11, 45, 47, 28, 31, 41], [31, 7, 0, 32, 18, 45, 47, 4, 7, 17], [20, 27, 26, 0, 13, 23, 25, 24, 27, 37], [34, 29, 40, 14, 0, 37, 39, 26, 29, 39], [34, 10, 3, 35, 21, 0, 2, 7, 10, 20], [37, 13, 6, 38, 24, 3, 0, 10, 13, 23], [48, 3, 24, 28, 14, 41, 43, 0, 3, 13], [45, 28, 21, 25, 11, 38, 40, 25, 0, 10], [35, 30, 23, 15, 1, 38, 40, 27, 2, 0]]
1
2
'
运行
运行

该算法的主要思想是通过动态规划来寻找图中的最短路径。首先，我们用一个二维数组dist来记录每个节点之间的最短距离。初始化时，我们将dist[i][j]设为正无穷，表示节点i到节点j之间没有路径。然后，我们依次枚举图中每个节点k，考虑通过节点k能否将路径i->j变得更短。如果存在一条路径i->k和一条路径k->j，并且它们长度之和比当前的最短路径i->j更短，则更新dist[i][j]的值为dist[i][k]+dist[k][j]。最终，dist数组中存储的就是每个节点之间的最短距离。

开发工具:Pycharm 2019.3
微信截屏工具Alt+A