山大公交线路上优化路径的查询实验报告 - 图文

山东大学 计算机科学与技术 学院

数据结构 课程实验报告

学号： 姓名： 班级： 实验题目：公交线路上优化路径的查询 实验学时：32 实验日期： 硬件环境： 软件环境： 实验内容与设计： 1.实验内容： 问题描述： 最短路径问题是图论中的一个经典问题，其中的Dijkstra算法一直被认为是图论中的好算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。 对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为： 线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；??；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。 例如：63：A(32,45)；B(76,45)；C(76,90)；??；N(100,100)。1元。5分钟。1/每分钟。 假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。 对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径等等。 基本要求： ① 根据上述公交线路的输入格式，定义并建立合适的图模型。 ② 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x：站名S，?，站名M1；换乘线路x：站名M1，?，站名M2；?；换乘线路x：站名MK，?，站名T。共花费x元。 ③ 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，?，站名M1；换乘线路x：站名M1，?，站名M2；?；换乘线路x：站名MK，?，站名T。共花费x时间。 ④ 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，?，站名M1；换乘线路x：站名M1，?，站名M2；?；换乘线路x：站名MK，?，站名T。共花费x时间。 实现提示： 需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。 2.实验设计: (1)实验需求： （1）输入数据：总的路线数目，各路线的站点数目，各站点的名称、位置坐标以及各公交路线的速度及票价。

1

（2）输出数据：输入数据的预处理结果（中间链表）与多个索引数组，三个不同权值的邻接矩阵的值（距离，时间，票价），以及各种不同需求下公交线路的结果。 （3）功能：实现在不同查询条件下最优公交线路的输出。 (2)实现思想： 首先需要对输入的数据进行预处理。此处运用双向链表来存储各站点的名称、横纵坐标及相对位置关系。然后用一个公交车Bus类来存储各个线路的票价、速度及总线路。 之后需要整合所有链表以生成邻接矩阵。首先将所有链表进行第一步处理，算出相邻两点间距离存入第一个结点中原横坐标的位置，特别的，每个链表最后一个站点对应结点的相同位置则存储为NoEdge（99999）。接着将各站点按顺序编号存于原链表纵坐标位置。接下来将各路线的链表连接在一起形成一个存有全部路线的新链表wholeRoad。 对wholeRoad进行处理。因为各路线中站点可能出现重复的情况，因此需要对编号进行去重操作。遍历链表若发现某站点名出现过两次或两次以上，则将第二个以后的编号皆赋成第一个的编号值，同时设置一个变量count来记录多次出现的的站点数。count初始值为0，若出现一次重复则count加1，同时后面所有的编号赋为原编号减去count。通过以上方法来解决重复站点问题。 根据最终站点编号建立原始编号与最终编号的索引数组和最终编号与站点名的索引数组，并提供逆向查找方法。最后生成以距离为邻接矩阵时依照的就是最终的编号。不过在生成过程中还是按照总线路链表进行循环，遍历总路线链表并根据索引将对应的距离存入真正的位置，其他位置均设为NoEdge。而生成以时间为权值和以票价为权值的邻接矩阵过程基本一样，只不过是将对应位置的值除相应速度或换为相应票价乘上线路编号的平方（原因下方解释）。 在最终邻接矩阵处理中主要运用Dijkstra算法。在时间最少与距离最短查询时直接使用Dijkstra算法即可。然而在票价最少时需要对算法进行调整。因为坐公交车时在一条线路上一直乘坐只需要交一次车票钱因此不能直接将票价进行累加，然而不同线路间也可能存在票价相同的情况，因此也不能直接运用只要和上一条路线票价相同就不进行累加的方法。为了避免不同线路票价权值相同，在赋值前先进行预处理，将票价改为相应票价乘上线路编号的平方，并建立索引以及添加一个寻找原票价的方法。因此对于最少花费查询，只需在Dijkstra算法中加上寻找原票价的方法以及判断将要添加的路径的权值是否与上一条相同的步骤。 最终结果是将存的点按索引转化为对应的站点名后按顺序输出，并将最小加权一并输出。先进行判断如果加权和仍为NoEdge，则输出“无路径!!”。边从属的路线的判断首先通过每个路线的链表将所有可能的路线按顺序存储起来，然后通过查找方法找到对应的路线名称即可。 (3)使用说明： 路线数，各站点坐标均为数字。查询方法选择时有效输入为1，2，3。其他输入会输出特定字符并结束程序。“是否继续时”只有输入y或Y才会继续。

2

(4)调试说明： 输入三条线路进行测试。距离、时间问题不大，主要通过设置第一个线路票价为3而第二、三条线路票价均为1且经过组合它们均可到达同一个地方（d）来测试最少花费的正确性。 大致线路图： 调试程序： 3

4