在交通网络非常发达、交通工具和交通方式不断更新的今天,
人们在出差、旅游或做其他出行时,不仅关心节省交通费用,而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题,通过建立交通网络图的存储结构图,提供用户查询的功能,功能一:通过输入城市名及任意两个城市的距离,查询任意两个城市之间的最短距离,从而达到最省目的;功能二:通过输入城市名以及任意两个程序的距离,查询中转路线最少。程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询,可以通过输入设置,延续程序的拓展性。
设计要求及分析
设计一个交通咨询系统,能让旅客咨询从任一个城市顶点到另一城市顶点之间的中转次数最少问题或最低花费或最少时间(最短路径)问题。
该设计共分三个部分:一是建立交通网络图的存储结构;二是解决单源最短路径问题;最后再实现任意两个城市顶点之间的最短路径问题。
1. 建立交通网络图的存储结构
要实现设计要求,首先要定义交通图的存储结构:邻接链表和邻接矩阵;
2. 解决任意两个城市顶点之间的中转次数最少的问题;
3. 解决任意两个城市顶点之间的最短路径(最低花费或最少时间)问题。
2021-07-08 14:02:43
23KB
c++
c
图