1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| graph = { 'A': {'B': 1, 'C': 4, 'D': 2}, 'B': {'A': 9, 'E': 5}, 'C': {'A': 4, 'F': 15}, 'D': {'A': 10, 'F': 7}, 'E': {'B': 3, 'J': 7}, 'F': {'C': 11, 'D': 14, 'K': 3, 'G': 9}, 'G': {'F': 12, 'I': 4}, 'H': {'J': 13}, 'I': {'G': 6, 'J': 7}, 'J': {'H': 2, 'I': 4}, 'K': {'F': 6} } source = input('输入起点 ')
came_from = {source:source}
passed_points = [source]
queue = {} for i in graph: queue[i] = float('inf') came_from[i] = None
queue[source] = 0
queue = sorted(queue.items(), key=lambda x: x[1]) while queue: min_point = queue.pop(0) queue = dict(queue) for i in graph[min_point[0]]: if i not in passed_points: comp = min_point[1] + graph[min_point[0]][i] if queue[i] > comp: queue[i] = comp came_from[i] = (min_point[0], comp) passed_points.append(i) queue = sorted(queue.items(), key=lambda x: x[1])
dest = input('输入终点 ') final_path = [] p = dest print('总共花费 ', came_from[p][1], ' 单位')
while came_from[p] != source: final_path.append(came_from[p][0]) p = came_from[p][0] for i in final_path[::-1]: print(i, end=' ')
|