2

要为 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 York City", 25 ],["Morristown", "Harrisburg", 150] 如何在 python 中制作这个矩阵？

这是结构：

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

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

非常感谢！

4

2 回答 2

1

如果您有 N 个城市，您将需要维度为 N x N 的矩阵。

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

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

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

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

于 2015-04-17T16:59:30.923 回答
0

如果您正在寻找快速查找，您可以考虑dict代替列表列表（权衡额外空间）

distance = {'Millburn': {'New York': 25}),
 'Morristown':  {'Harrisburg': 150}),
 'New York City': {'Philadelphia': 97}),
 'Philadelphia':  {'New York City': 120})}

（注意插入反向边缘和值）

您可以使用defaultdict您给定的数组创建像上面那样的字典。

from collections import defaultdict
roads = [["Philadelphia", "New York City", 120 ], ["New York City", "Philadelphia", 97 ],[ "Millburn", "New York", 25 ],["Morristown", "Harrisburg", 150]]
d = defaultdict(lambda : defaultdict(lambda:0))
for source,dest,distance in roads:
    d[source][dest] = distance

如果您使用的是pandas，则可以将上述字典转换为 pandas 数据框。

import pandas
dist = pandas.DataFrame.from_dict(distance)
print dist
#               Millburn  Morristown  New York City  Philadelphia
#Harrisburg          NaN         150            NaN           NaN
#New York             25         NaN            NaN           NaN
#New York City       NaN         NaN            NaN           120
#Philadelphia        NaN         NaN             97           NaN
dist['Philadelphia']['New York City']
# 120.0
于 2015-04-17T15:18:55.897 回答