要为 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 算法即可。
