数据结构-图-公交线路查询.pdfVIP

数据结构- 图 ——公交线路查询 • 功能实现 • 最短路径算法 • 输出结果展示 • 实现的功能： • 内置路径 • 最短距离 • 查询 最少时间 最少花费 • 删除路线 • 添加路线 无向图，邻接表存储方式 • 每一条边定义为一个结构， 包含6个参数。 最短路径算法 • Dijkstra 算法 • 根据已经确定了的点的距离，来确定该点相邻顶点的距离，不断的 向外散射，直到所以的点的到起点的最短距离确定为止。 将所有顶点到起始点的最短距离存在一张表里，随时调用。 • 初始化顶点信息 将起点s的dist 字段设为0; • 输入的起点为v • 从所有顶点中找到与v 相邻的顶点 • 找到这些顶点中dist最小的并且known 为false的h ，然后，将该顶点h的 known 置为true; • 然后更新与顶点h相邻的所有其它known 为false的顶点w的dist 和path的 值。 • 如果h.dist+distance(h,w) w.dist; 则更新w.dist = h.dist + distance(v,w);(distance(v,w) 就是表示权值) w.path=h; • 遍历完所有的顶点，则 终止。 得到了存储了各个顶点到 起点的最短路径的表， 通过查表，就可以输出 最短路径和相应的路线。 查询： 输入起点与终点 输出最短距离，及相应路线 最少时间，及相应路线 最少花费，及相应路线 • 路线的输出 需要从最短路径表中， 从终点向起点方向逐个寻点， 再反方向输出。 • 删除路线： • 测试结果： • 添加路线： 比如说，添加一条地铁线 • 添加线路后的输出结果： 未添加路线时（左图） •存在的不足： • 虽然统计出了每两点之间是坐地铁还是公交，但是换成次数尚未实 现 • 时间有限，图形化界面设计没有实现 谢谢大家！