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 に答える