0
所以我在這裏得到了這個代碼，它將圖形打印出來，然後打印出兩個點之間的最短距離。它的輸入是蟒蛇filename.py開始結束的map.txt 它與圖我已經給它像這樣一個偉大工程：Dijkstra算法打印太多
{'a': {'b': 5, 'c': 8},
'b': {'a': 5, 'd': 6},
'c': {'a': 8, 'd': 2},
'd': {'b': 6, 'c': 2, 'e': 12, 'f': 2},
'e': {'d': 12, 'g': 3},
'f': {'d': 2, 'g': 7},
'g': {'e': 3, 'f':7}}
唯一的問題是，當它打印輸出的命令，它打印它是這樣的：
從開始到結束的距離是（距離，[開始，結束]） 我不明白tot如何打印沒有任何圓括號或開始和結束點的距離。任何幫助表示讚賞。
「」」 冬季2014 作者：科爾夏博諾&彼得·範 信用：Python: Importing a graph ＃1幫助我們找出如何通過sys.argv中
Finds the shortest path between two points in a dictionary graph.
Uses a single-source shortest distance approach, nearly identical to
Dijkstra's Algortihm.
Takes input in the format: python filename.py start end grap.txt
"""
import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
"""Finds the shortest path between a start and end point from a graph"""
if start==end:
path=[] ##If the starting point is the end point, then we're done
while end != None:
path.append(end)
end=predecessors.get(end,None)
return distances[start], path[::-1]
##Check if it's the first time through it, and set current distance to 0
if not visited: distances[start]=0
##Runs through each adjacent point, and keeps track of the preceeding ones
for neighbor in graph[start]:
if neighbor not in visited:
neighbordist = distances.get(neighbor,sys.maxsize)
tentativedist = distances[start] + graph[start][neighbor]
if tentativedist < neighbordist:
distances[neighbor] = tentativedist
predecessors[neighbor]=start
##Now that all of the adjacent points are visited, we can mark the current point as visited
visited.append(start)
##This finds the next closest unvisited point to start on
unvisiteds = dict((k, distances.get(k,sys.maxsize)) for k in graph if k not in visited)
closestvertex = min(unvisiteds, key=unvisiteds.get)
##Recurses that closest point making it the current one
return shortestpath(graph,closestvertex,end,visited,distances,predecessors)
if __name__ == "__main__":
start = sys.argv[1]
end = sys.argv[2]
graph = eval(open(sys.argv[3],'r').read())
if len(sys.argv) != 4:
print('Input syntax: python filename.py start end map.py')
else:
print('Distance from ',start,' to ',end,' is ',shortestpath(graph,start,end))
"""
Result:
(20, ['a', 'y', 'w', 'b'])
"""