《数据结构-图-公交线路查询》由会员分享，可在线阅读，更多相关《数据结构-图-公交线路查询（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构-图公交线路查询功能实现最短路径算法输出结果展示实现的功能：内置路径 最短距离 查询最少时间最少花费 删除路线添加路线无向图，邻接表存储方式每一条边定义为一个结构，包含6个参数。最短路径算法Dijkstra算法根据已经确定了的点的距离，来确定该点相邻顶点的距离，不断的 向外散射，直到所以的点的到起点的最短距离确定为止。将所有顶点到起始点的最短距离存在一张表里，随时调用。初始化顶点信息将起点s的dist字段设为0;输入的起点为v 从所有顶点中找到与v相邻的顶点 找到这些顶点中dist最小的并且known为false的h，然后，将该顶点h的 known置为true; 然后更新与顶点h相邻的
2、所有其它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;遍历完所有的顶点，则终止。得到了存储了各个顶点到起点的最短路径的表，通过查表，就可以输出最短路径和相应的路线。查询： 输入起点与终点 输出最短距离，及相应路线 最少时间，及相应路线 最少花费，及相应路线 路线的输出 需要从最短路径表中， 从终点向起点方向逐个寻点， 再反方向输出。删除路线：测试结果：添加路线：比如说，添加一条地铁线添加线路后的输出结果：未添加路线时（左图）存在的不足：虽然统计出了每两点之间是坐地铁还是公交，但是换成次数尚未实 现时间有限，图形化界面设计没有实现谢谢大家！
