Skip to main content
 首页 » 编程设计

python之距离矩阵 FLoyd Warshall Python

2025年05月04日12telwanggs

要为 Floyd Warshall 算法“最短路径”( https://www.cs.usfca.edu/~galles/visualization/Floyd.html?hc_location=ufi ) 创建距离矩阵,您需要将一些道路作为顶点,并将这些道路之间的距离作为边。例如(出发地、目的地、距离):roads = [["Philadelphia", "New York City", 120 ], ["New York City", "Philadelphia", 97 ],[ "Millburn, "New约克市”, 25 ],[“莫里斯敦”, “哈里斯堡”, 150] 我怎样才能在 python 中制作这个矩阵?

这是结构:

network[0] = #list destinations 
for i in range (len(roads)): 
      network [i][0] = #list departures 

我不知道如何在正确的位置填充距离,因为 network[roads[i][0],[roads[i][1]] 不正确多次使用目的地或出发地时的解决方案。

非常感谢!

请您参考如下方法:

如果您有 N 个城市,则需要 N x N 维矩阵。

首先,您必须将城市映射到数字。

'Millburn' : 0 
'Morristown': 1 
... 

计算城市数量 - N 并制作 N x N 维度的空矩阵。现在将矩阵 (i, j) 的每个条目设置为城市 i 和 j 之间的距离。如果不存在直接连接,则将值设置为无穷大。

获得该矩阵后,只需在其上运行 FLoyd Warshall 算法即可。