Python的最短距離

我想寫一個程序，返回從點A到點E的最短距離。我編碼得到的長度，但我不知道如何實際得到的點。Python的最短距離

enter image description here

d = {("A","A"):0, ("A","B"):1, ("A","C"):3, ("A","D"):7 , ("A","E"):101, 
      ("B","A"):101, ("B","B"):0, ("B","C"):42, ("B","D"):6, ("B","E"):27, 
      ("C","A"):101, ("C","B"):101, ("C","C"):0, ("C","D"):2, ("C","E"):13, 
      ("D","A"):101, ("D","B"):101, ("D","C"):101, ("D","D"):0, ("D","E"):5, 
      ("E","A"):101, ("E","B"):101, ("E","C"):101, ("E","D"):101, ("E","E"):0 
    } 

def shortestPath(Cities,Distances): 
'''Returns the length of the shortest path from the first city in the list to the last city in the list, using only cities that appear in that list.''' 
    if len(Cities)==1: return 0 
    else: return min(map(lambda n: (Distances[Cities[0],Cities[n]] + shortestPath(Cities[n:],Distances)), range(1,len(Cities))))

答案輸入：最短路徑（[ 「A」，「B」，「C」，「d」，「E」]，d）是10。但是該程序也應該輸出距離，所以答案應該是[10，[「A」，「C」，「D」，「E」]]

來源

2012-09-28 user1681664

所以...你希望我們調試你的程序？或者你的具體問題是什麼？你是否自己做了一些調試，比如看看'map'的結果是什麼？ –

爲什麼你用這種方式編寫最短路徑算法？它是強制性的嗎？否則，您可以使用[Dijkstra的SPA]（http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode），因爲有一種簡單的方法來重新創建最短路徑。 –

如果你有決心保持在一個肉行，你可以做一個小的改變了代碼：

def track_past_city(x,y): 
    return (x[0]+y[0],x[1:]+y[1:]) #0 is how far you've gone, #[1:] is where you've been 

def shortestPath(Cities,Distances): 
    if len(Cities)==1: return 0, Cities[0] 
    else: return min(map(lambda n: (track_past_city((Distances[Cities[0],Cities[n]],Cities[0]),shortestPath(Cities[n:],Distances))), range(1,len(Cities)))) 


shortestPath(["A","B", "C", "D", "E"],d) 
# (10, ('A', ('C', ('D', 'E'))))

我不是很肯定如何應對的錯誤元組發生增加，但由此你應該能夠調整你自己的解決方案...

注意：這帶有一個健康警告，你不應該在一行寫所有的代碼，它很難閱讀，很難調試，一般一個壞主意。

來源

2012-09-28 23:44:29

看起來像一個典型的最短路徑問題。明顯的方法是使用dijkstra，但有更酷的算法。例如，這一次我在一個codegolf會話黑客：

G,S,T=input();J={n:9e9if n!=T else 0for n in G} 
while J[S]>1e9:J={n:0if n==T else min(c+J[d]for d,c in G[n].items())for n in G} 
while S!=T:print S;S=min((c+J[d],d)for d,c in G[S].items())[1]

你不得不雖然改變你的圖形表示，但對於該輸入（你的轉述圖）輸出正確的最短路徑：

{'A': {'C': 3, 'B': 1, 'D': 7}, 'C': {'A': 3, 'B': 42, 'E': 13, 'D': 2}, 'B': {'A': 1, 'C': 42, 'E': 27, 'D': 6}, 'E': {'C': 13, 'B': 27, 'D': 5}, 'D': {'A': 7, 'B': 6, 'E': 5}}, 'A', 'E'

所以...閱讀圖算法，他們並不難。如果你拒絕這麼做：祝你好運理解我的codegolfed定點算法。

來源

2012-09-28 23:19:29 ch3ka

+1爲Djikstra和高爾夫幽默。 – jamylak

Python的最短距離

回答

相關問題