根据这个,结合数据结构有向图的相关知识,写出这个程序的代码

时间: 2024-03-09 15:45:07 浏览: 18
好的,以下是一个简单的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程序,用于实现您所要求的全国交通咨询模拟系统。由于程序的实现方式和您的具体要求可能存在差异,如有需要可以进行适当的修改。

相关推荐

最新推荐

recommend-type

校园导游-数据结构课程设计(附源代码)

设计一个校园导游,提供行走线路...(1)根据用户需求智能推荐相关地点。 (2)粗略展示校园平面图。 (3)罗列各个景点,实现对某个景点的详细查询。 (4)给出到某个景点的最佳路线。 (5)管理员可以修改景点信息。
recommend-type

数据结构程序设计.docx

1) 建立学生档案管理的数据结构和存储结构; 2) 完成学生档案管理数据的基本操作; 3) 为提高管理效率,尝试设计较好的面向应用的查找存储结构,如二叉排序树。 2.实验任务: 设计一个学生档案管理信息系统,管理的...
recommend-type

Python 判断 有向图 是否有环的实例讲解

在Python编程中,判断有向图(Directed Graph)是否存在环是一项常见的任务,特别是在处理图算法时。本实例将介绍一种使用深度...在实际应用中,根据具体情况可能需要对代码进行调整以适应不同的数据结构或输入格式。
recommend-type

数据结构综合课设地图着色问题.docx

一、问题描述 设计地图着色软件,对江西地图中...1.地图采用图型数据结构,每个地级市为一个节点,边表示对应的两个地级市相邻。 2.设计着色算法,保证临接点不是同一种颜色。 3.演示程序以用户和计算机的对话方式进行
recommend-type

微信小程序图片右边加两行文字的代码

在微信小程序开发中,有时我们需要将图片与文字结合展示,例如让图片位于右侧,而文字则在图片旁边。本篇文章将详细讲解如何实现这一功能,通过具体的WXML和WXSS代码示例,帮助开发者更好地理解和应用。 首先,我们...
recommend-type

BSC关键绩效财务与客户指标详解

BSC(Balanced Scorecard,平衡计分卡)是一种战略绩效管理系统,它将企业的绩效评估从传统的财务维度扩展到非财务领域,以提供更全面、深入的业绩衡量。在提供的文档中,BSC绩效考核指标主要分为两大类:财务类和客户类。 1. 财务类指标: - 部门费用的实际与预算比较:如项目研究开发费用、课题费用、招聘费用、培训费用和新产品研发费用,均通过实际支出与计划预算的百分比来衡量,这反映了部门在成本控制上的效率。 - 经营利润指标:如承保利润、赔付率和理赔统计,这些涉及保险公司的核心盈利能力和风险管理水平。 - 人力成本和保费收益:如人力成本与计划的比例,以及标准保费、附加佣金、续期推动费用等与预算的对比,评估业务运营和盈利能力。 - 财务效率:包括管理费用、销售费用和投资回报率,如净投资收益率、销售目标达成率等,反映公司的财务健康状况和经营效率。 2. 客户类指标: - 客户满意度:通过包装水平客户满意度调研,了解产品和服务的质量和客户体验。 - 市场表现:通过市场销售月报和市场份额,衡量公司在市场中的竞争地位和销售业绩。 - 服务指标:如新契约标保完成度、续保率和出租率,体现客户服务质量和客户忠诚度。 - 品牌和市场知名度:通过问卷调查、公众媒体反馈和总公司级评价来评估品牌影响力和市场认知度。 BSC绩效考核指标旨在确保企业的战略目标与财务和非财务目标的平衡,通过量化这些关键指标,帮助管理层做出决策,优化资源配置,并驱动组织的整体业绩提升。同时,这份指标汇总文档强调了财务稳健性和客户满意度的重要性,体现了现代企业对多维度绩效管理的重视。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

【实战演练】俄罗斯方块:实现经典的俄罗斯方块游戏,学习方块生成和行消除逻辑。

![【实战演练】俄罗斯方块:实现经典的俄罗斯方块游戏,学习方块生成和行消除逻辑。](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/70a49cc62dcc46a491b9f63542110765~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp) # 1. 俄罗斯方块游戏概述** 俄罗斯方块是一款经典的益智游戏,由阿列克谢·帕基特诺夫于1984年发明。游戏目标是通过控制不断下落的方块,排列成水平线,消除它们并获得分数。俄罗斯方块风靡全球,成为有史以来最受欢迎的视频游戏之一。 # 2.
recommend-type

卷积神经网络实现手势识别程序

卷积神经网络(Convolutional Neural Network, CNN)在手势识别中是一种非常有效的机器学习模型。CNN特别适用于处理图像数据,因为它能够自动提取和学习局部特征,这对于像手势这样的空间模式识别非常重要。以下是使用CNN实现手势识别的基本步骤: 1. **输入数据准备**:首先,你需要收集或获取一组带有标签的手势图像,作为训练和测试数据集。 2. **数据预处理**:对图像进行标准化、裁剪、大小调整等操作,以便于网络输入。 3. **卷积层(Convolutional Layer)**:这是CNN的核心部分,通过一系列可学习的滤波器(卷积核)对输入图像进行卷积,以
recommend-type

绘制企业战略地图:从财务到客户价值的六步法

"BSC资料.pdf" 战略地图是一种战略管理工具,它帮助企业将战略目标可视化,确保所有部门和员工的工作都与公司的整体战略方向保持一致。战略地图的核心内容包括四个相互关联的视角:财务、客户、内部流程和学习与成长。 1. **财务视角**:这是战略地图的最终目标,通常表现为股东价值的提升。例如,股东期望五年后的销售收入达到五亿元,而目前只有一亿元,那么四亿元的差距就是企业的总体目标。 2. **客户视角**:为了实现财务目标,需要明确客户价值主张。企业可以通过提供最低总成本、产品创新、全面解决方案或系统锁定等方式吸引和保留客户,以实现销售额的增长。 3. **内部流程视角**:确定关键流程以支持客户价值主张和财务目标的实现。主要流程可能包括运营管理、客户管理、创新和社会责任等,每个流程都需要有明确的短期、中期和长期目标。 4. **学习与成长视角**:评估和提升企业的人力资本、信息资本和组织资本,确保这些无形资产能够支持内部流程的优化和战略目标的达成。 绘制战略地图的六个步骤: 1. **确定股东价值差距**:识别与股东期望之间的差距。 2. **调整客户价值主张**:分析客户并调整策略以满足他们的需求。 3. **设定价值提升时间表**:规划各阶段的目标以逐步缩小差距。 4. **确定战略主题**:识别关键内部流程并设定目标。 5. **提升战略准备度**:评估并提升无形资产的战略准备度。 6. **制定行动方案**:根据战略地图制定具体行动计划,分配资源和预算。 战略地图的有效性主要取决于两个要素: 1. **KPI的数量及分布比例**:一个有效的战略地图通常包含20个左右的指标,且在四个视角之间有均衡的分布,如财务20%,客户20%,内部流程40%。 2. **KPI的性质比例**:指标应涵盖财务、客户、内部流程和学习与成长等各个方面,以全面反映组织的绩效。 战略地图不仅帮助管理层清晰传达战略意图,也使员工能更好地理解自己的工作如何对公司整体目标产生贡献,从而提高执行力和组织协同性。