数据结构课程设计(0) 抽题 + 初步思路

今天上午收到了数据结构课程设计的课题,午睡时想出了一种能简洁的解决问题但时空效率不是太高的算法。

题意

公交线路上的优化路径查询

问题描述

最短路径问题是图论中的一个经典问题,其中的Dijkstra算法一直被认为是图论中的好算法,但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的査询。

对于某城市的公交线路,乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。

设该城市的公交线路的输入格式为:

线路编号: 起始站名(该站坐标); 经过的站点1名(该站坐标); 经过的站点2名(该站坐标); 经过的站点n名(该站坐标); 终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。

例如:63: A(32,45); B(76,45); C(76,90); ...; N(100,100)。1元。5分钟。1/每分钟。假定线路的乘坐价钱与乘坐站数无关,假定不考虑公交线路在路上的交通堵塞。对这样的公交线路,需要在其上进行的优化路径查询包括任何两个站点之间最便宜的路径任何两个站点之间最省时间的路径等等。

基本要求

  1. 根据上述公交线路的输入格式,定义并建立合适的图模型。
  2. 针对上述公交线路,能查询获得任何两个站点之间最便宜的路径,即输入站名S, T后,可以输出从S到T的最便宜的路径,输出格式为:线路x: 站名S, ..., 站名M1; 换乘线路x: 站名M1, ..., 站名M2; 换乘线路x站名MK, ..., 站名T。共花费x元。
  3. 针对上述公交线路,能查询获得任何两个站点之间最省时间的路径(不考虑在中间站等下一辆线路的等待时间),即输入站名S, T后,可以输出从S到T的考虑在中间站等下辆线路的等待时间的最省时间的路径,输出格式为:线路x: 站名S, ..., 站名M1; 换乘线路x: 站名M1, ...,站名M2; 换乘线路x: 站名MK, ..., 站名T。共花费x时间。
  4. 针对上述公交线路,能查询获得任何两个站点之间最省时间的路径(要考虑在中间站等下一辆线路的等待时间),即输入站名S, T后,可以输出从S到T的考虑在中间站等下辆线路的等待时间的最省时间的路径,输出格式为:线路x: 站名S,..., 站名M1; 换乘线路x: 站名M1, ..., 站名M2; 换乘线路x: 站名MK, ..., 站名T。共花费x时间。

实现提示

需深入考虑,应根据不同的应用目标,即不同的优化査询来建立合适的图模型。

思路

目前我的想法是:先每条线路各自独立地按照线路顺序连接起来,比如现在有三条线路,A1->B1->C1->D1->E1, C2->B2->F2->A2, E3->D3->A3->B3,就需要建立13个点10条边,权值为距离/速度(如果是求最便宜的路径则为0)。然后考虑换乘的情况,比如当前乘坐第3条线到了A站点,在A站点可以换乘第1或第3条线,此时我可以建立一个虚拟结点A0,让A1A2A3连接到这个点上,权值为0,然后此虚拟结点A0也连接到A1A2A3上,权值为对应结点的平均等待时间(价钱),表示可以在此点下车换乘。然后从S点开始用Dijkstra求一遍单源最短路,路径只需记录由哪个点更新而来再反推即可。这样复杂度不是太理想,因为最坏情况可以有$O(nm)$个点(n为站点数,m为线路数),$O(nm)$条边。

后续工作

思考优化算法,并使用QT编写交互良好的GUI对算法运行结果进行展示。

如果您觉得这篇文章对您有帮助,请随意打赏。