距離矩陣FLoyd Warshall Python

要爲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中創建這個矩陣？距離矩陣FLoyd Warshall Python

這是結構：

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

我不知道如何填寫正確的位置的距離，因爲network[roads[i][0],[roads[i][1]]是不是當一個目的地或出發時使用更多的時間比一個合適的解決方案。

非常感謝！

來源

2015-04-17 Materials

如果您正在尋找快速查找，您可以考慮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，你可以將上面的字典到大熊貓數據幀。

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-17 15:18:55 srj

恐怕我不能使用熊貓...這就是爲什麼我認爲使用字典更復雜，因爲這些是無序的，你不能通過索引選擇元素。這很重要，因爲我不能使用例如「距離[Millburn]」，所以我必須構建一個通用矩陣，它與每個給定的道路元組一起工作。 – Materials

@Materials，我已經編輯了答案，以顯示如何從您提供的數組創建詞典。所以構建通用矩陣不是問題。請詳細說明您是否需要使用整數索引而不是字符串索引;因爲這將是微不足道的。 – srj

@Materials，如果您可以編輯問題，並提供關於如何使用數據結構的信息，則有人可以幫助您創建該數據結構 – srj

如果你有N個城市，你將需要尺寸的N×N的矩陣

首先，你必須映射城市數字。城市

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

計數數 - N和使尺寸的N×N的空矩陣現在設置矩陣（I，J）的每個條目城市i和j之間拉開距離。如果不存在直接連接設置值到無窮大。

一旦你有了這個矩陣，就運行FLoyd Warshall算法。

來源

2015-04-17 16:59:30 Riko

距離矩陣FLoyd Warshall Python

回答

相關問題