python - 距离矩阵 FLoyd Warshall Python

Question

要为 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]] 不正确多次使用目的地或出发地时的解决方案。

非常感谢!

Answer 1

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

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

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

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

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