根据这个,结合数据结构有向图的相关知识,写出这个程序的代码
时间: 2024-03-09 19:45:07 浏览: 14
好的,以下是一个简单的Python程序,用于实现您所要求的全国交通咨询模拟系统。该程序基于有向图的相关知识,使用Dijkstra算法计算两个城市之间的最短路径和最短时间,并使用贪心算法计算最小花费路径。程序中使用了Python的面向对象编程思想,将城市、铁路和路径等信息封装为对象,使程序的结构更加清晰。
```python
import heapq
class City:
def __init__(self, name, intro):
self.name = name
self.intro = intro
self.railways = []
def add_railway(self, railway):
self.railways.append(railway)
class Railway:
def __init__(self, start_city, end_city, distance, speed, cost):
self.start_city = start_city
self.end_city = end_city
self.distance = distance
self.speed = speed
self.cost = cost
class Path:
def __init__(self, start_city, end_city, distance, time, cost, route):
self.start_city = start_city
self.end_city = end_city
self.distance = distance
self.time = time
self.cost = cost
self.route = route
class Graph:
def __init__(self):
self.cities = {}
def add_city(self, city):
self.cities[city.name] = city
def add_railway(self, start_city_name, end_city_name, distance, speed, cost):
start_city = self.cities[start_city_name]
end_city = self.cities[end_city_name]
railway = Railway(start_city, end_city, distance, speed, cost)
start_city.add_railway(railway)
def dijkstra_shortest_path(self, start_city_name, end_city_name, mode="distance"):
start_city = self.cities[start_city_name]
end_city = self.cities[end_city_name]
visited = {}
distance = {}
previous = {}
for city_name in self.cities:
distance[city_name] = float("inf")
visited[city_name] = False
previous[city_name] = None
distance[start_city_name] = 0
heap = [(0, start_city_name)]
while heap:
(d, current_city_name) = heapq.heappop(heap)
if visited[current_city_name]:
continue
visited[current_city_name] = True
if current_city_name == end_city_name:
break
current_city = self.cities[current_city_name]
for railway in current_city.railways:
if mode == "distance":
weight = railway.distance
elif mode == "time":
weight = railway.distance / railway.speed
elif mode == "cost":
weight = railway.distance * railway.cost
neighbor_city_name = railway.end_city.name
tentative_distance = distance[current_city_name] + weight
if tentative_distance < distance[neighbor_city_name]:
distance[neighbor_city_name] = tentative_distance
previous[neighbor_city_name] = current_city_name
heapq.heappush(heap, (distance[neighbor_city_name], neighbor_city_name))
path = []
current_city_name = end_city_name
while current_city_name != start_city_name:
previous_city_name = previous[current_city_name]
current_city = self.cities[current_city_name]
previous_city = self.cities[previous_city_name]
for railway in current_city.railways:
if railway.start_city == previous_city and railway.end_city == current_city:
path.insert(0, railway)
break
current_city_name = previous_city_name
if mode == "distance":
return Path(start_city, end_city, distance[end_city_name], None, None, path)
elif mode == "time":
time = distance[end_city_name] / path[-1].speed
return Path(start_city, end_city, distance[end_city_name], time, None, path)
elif mode == "cost":
cost = distance[end_city_name] * path[-1].cost
return Path(start_city, end_city, distance[end_city_name], None, cost, path)
def display_menu():
print("请选择要进行的操作:")
print("1. 显示城市信息")
print("2. 查询最短路程")
print("3. 查询最短时间")
print("4. 查询最小花费")
print("5. 增加新的城市")
print("6. 退出程序")
def display_city_info(city):
print(city.intro)
def display_path(path):
print("最短路程:", path.distance, "km")
if path.time is not None:
print("最短时间:", path.time, "h")
if path.cost is not None:
print("最小花费:", path.cost, "元")
print("路线规划:")
for railway in path.route:
print(railway.start_city.name, "->", railway.end_city.name, "(", railway.distance, "km)")
def main():
graph = Graph()
# 添加城市
beijing = City("北京", "北京是中国的首都。")
shanghai = City("上海", "上海是中国的经济中心。")
guangzhou = City("广州", "广州是中国的南方大城市。")
shenzhen = City("深圳", "深圳是中国的特别行政区之一。")
chengdu = City("成都", "成都是中国的西南大城市。")
graph.add_city(beijing)
graph.add_city(shanghai)
graph.add_city(guangzhou)
graph.add_city(shenzhen)
graph.add_city(chengdu)
# 添加铁路
graph.add_railway("北京", "上海", 1318, 300, 0.5)
graph.add_railway("北京", "广州", 2319, 250, 0.4)
graph.add_railway("北京", "深圳", 2320, 250, 0.4)
graph.add_railway("北京", "成都", 1444, 200, 0.3)
graph.add_railway("上海", "广州", 1210, 300, 0.5)
graph.add_railway("上海", "深圳", 1462, 300, 0.5)
graph.add_railway("上海", "成都", 1942, 250, 0.4)
graph.add_railway("广州", "深圳", 147, 200, 0.3)
graph.add_railway("广州", "成都", 1430, 200, 0.3)
graph.add_railway("深圳", "成都", 1426, 200, 0.3)
while True:
display_menu()
choice = input("请输入要进行的操作编号:")
if choice == "1":
city_name = input("请输入要查询的城市名称:")
city = graph.cities[city_name]
display_city_info(city)
elif choice == "2":
start_city_name = input("请输入出发城市名称:")
end_city_name = input("请输入到达城市名称:")
path = graph.dijkstra_shortest_path(start_city_name, end_city_name, "distance")
display_path(path)
elif choice == "3":
start_city_name = input("请输入出发城市名称:")
end_city_name = input("请输入到达城市名称:")
path = graph.dijkstra_shortest_path(start_city_name, end_city_name, "time")
display_path(path)
elif choice == "4":
start_city_name = input("请输入出发城市名称:")
end_city_name = input("请输入到达城市名称:")
path = graph.dijkstra_shortest_path(start_city_name, end_city_name, "cost")
display_path(path)
elif choice == "5":
city_name = input("请输入要添加的城市名称:")
city_intro = input("请输入要添加的城市介绍:")
city = City(city_name, city_intro)
graph.add_city(city)
print("城市添加成功。")
elif choice == "6":
break
else:
print("无效的操作编号,请重新输入。")
if __name__ == "__main__":
main()
```
以上是一个简单的Python程序,用于实现您所要求的全国交通咨询模拟系统。由于程序的实现方式和您的具体要求可能存在差异,如有需要可以进行适当的修改。