算法_校园最短路径漫游设计

import heapq # 定义图类 class Graph: def __init__(self): self.adjacency_list = {} def add_vertex(self, vertex): if vertex not in self.adjacency_list: self.adjacency_list[vertex] = {} def add_edge(self, vertex1, vertex2, distance): self.adjacency_list[vertex1][vertex2] = distance self.adjacency_list[vertex2][vertex1] = distance def get_neighbors(self, vertex): return self.adjacency_list[vertex] # 实现Dijkstra算法 def dijkstra(graph, start_vertex): distances = {vertex: float('inf') for vertex in graph.adjacency_list} distances[start_vertex] = 0 pq = [(0, start_vertex)] while pq: current_distance, current_vertex = heapq.heappop(pq) if current_distance > distances[current_vertex]: continue for neighbor, distance in graph.get_neighbors(current_vertex).items(): path_cost = distances[current_vertex] + distance if path_cost < distances[neighbor]: distances[neighbor] = path_cost heapq.heappush(pq, (path_cost, neighbor)) return distances # 创建校园地图图例 def create_campus_map(): campus_map = Graph() # 添加各主要场所 places = ['Place1', 'Place2', 'Place3', ...] for place in places: campus_map.add_vertex(place) # 添加场所之间的连接边 campus_map.add_edge('Place1', 'Place2', 5) # 例如：Place1到Place2距离为5 campus_map.add_edge('Place2', 'Place3', 10) ... return campus_map def main(): campus_map = create_campus_map() # 获取起点和终点 start_place = input('请输入起点: ') end_place = input('请输入终点: ') # 计算最短路径 distances = dijkstra(campus_map, start_place) shortest_distance = distances[end_place] print('最短路径距离: ', shortest_distance) if __name__ == '__main__': main()