设计一个简单的旅游交通线路查询系统,当输入多个地点和地点间的距离和路费后,计算出最合理的路线规划并输出结果,要求算法的时间复杂度较低,并列出详细代码
时间: 2024-03-20 19:43:44 浏览: 20
好的,下面是一个简单的旅游交通线路查询系统的实现,主要使用Dijkstra算法来计算最短路径。
```python
import heapq
class Graph:
def __init__(self):
self.edges = {}
def add_edge(self, from_node, to_node, distance, cost):
if from_node not in self.edges:
self.edges[from_node] = {}
self.edges[from_node][to_node] = (distance, cost)
def dijkstra(self, start_node, end_node):
distances = {node: float('inf') for node in self.edges}
distances[start_node] = 0
queue = [(0, start_node, [])]
while queue:
(distance, current_node, path) = heapq.heappop(queue)
if distances[current_node] < distance:
continue
path = path + [current_node]
if current_node == end_node:
return (distance, path)
for neighbor, (neighbor_distance, neighbor_cost) in self.edges[current_node].items():
new_distance = distance + neighbor_distance
new_cost = neighbor_cost
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
heapq.heappush(queue, (new_distance, neighbor, path))
return -1, []
if __name__ == '__main__':
# 构建图
g = Graph()
g.add_edge('A', 'B', 10, 100)
g.add_edge('A', 'C', 3, 50)
g.add_edge('B', 'C', 1, 20)
g.add_edge('B', 'D', 2, 10)
g.add_edge('C', 'B', 4, 20)
g.add_edge('C', 'D', 8, 30)
g.add_edge('C', 'E', 2, 60)
g.add_edge('D', 'E', 7, 10)
g.add_edge('E', 'D', 9, 50)
# Dijkstra算法计算最短路径
start_node = 'A'
end_node = 'D'
distance, path = g.dijkstra(start_node, end_node)
# 输出结果
if distance == -1:
print(f"No path found from {start_node} to {end_node}")
else:
print(f"The shortest distance from {start_node} to {end_node} is {distance}")
print(f"The path is {' -> '.join(path)}")
```
这段代码中,首先定义了一个Graph类,用于表示无向图。在构建图时,使用add_edge方法添加节点之间的边,并记录距离和路费。
接着,使用Dijkstra算法计算最短路径。我们使用了一个distances字典来记录每个节点到起点的距离,初始时将所有节点的距离设为无穷大。然后,我们使用一个优先队列(即heapq)来存储未标记的节点,并按照距离起点的距离进行排序。每次选择未标记的节点中距离起点最近的一个节点作为下一个计算的节点,并更新与该节点相邻的节点的最短距离。直到找到终点或者所有节点都被标记。
最后,输出起点到终点的最短距离和路线即可。
注意:这里的实现并没有考虑输入数据的合法性和异常情况,需要根据具体情况进行完善。