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'])
"""