写出代码实现:假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要场所,弧代表已有的公交线路,弧上的权表示该线路上的票价(或搭乘所需时间),试设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
时间: 2024-02-25 16:59:33 浏览: 16
好的,我来为您提供一个基于 Dijkstra 算法的最短路径算法的实现代码,您可以根据您的具体需求进行优化:
```python
import heapq
def dijkstra(graph, start, end, mode):
"""
:param graph: 带权有向图,使用邻接表表示
:param start: 起点
:param end: 终点
:param mode: 模式,0为最短时间,1为最小票价
:return: 最短路径及其权重
"""
heap = [(0, start, [])] # 使用堆优化,(权重, 当前节点, 当前路径)
visited = set() # 记录已访问节点
while heap:
(weight, current_node, current_path) = heapq.heappop(heap)
if current_node not in visited:
visited.add(current_node)
current_path = current_path + [current_node]
if current_node == end:
return current_path, weight
for (neighbor, neighbor_weight) in graph[current_node].items():
if neighbor not in visited:
if mode == 0: # 最短时间
heapq.heappush(heap, (weight + neighbor_weight, neighbor, current_path))
else: # 最小票价
heapq.heappush(heap, (weight + 1, neighbor, current_path))
return None, None
```
其中,graph 表示图的邻接表,start 表示起点,end 表示终点,mode 表示模式,0 表示最短时间,1 表示最小票价。函数返回最短路径及其权重。