拓展篇- 最短路径计算
最短路径计算是车载导航的基本功能，迪杰斯特拉 (Dijkstra)是典型的单源最短路径算法，用于计算某节点到其他节点的最短路径。
图1是带权有向图，设为G=(V,E)，图中的顶点集合为{武大，地大，华工，光谷，图书城}，线上所标注的为相邻线段之间车辆行驶时间，即权重。请使用Dijkstra算法求“武大”到各顶点的最短路径。
图1 路网示意图
一、数据文件读取
编写程序读取“路径数据.txt”文件，数据内容和格式说明如表1所示，每1行是1条有向线段，格式为“起点，终点，权值”。
表1 数据内容和格式说明
| 数据内容 | 格式说明 |
| 武大,地大,6
武大,光谷,11 武大,图书城,24 地大,光谷,4 地大,华工,8 光谷,地大,5 光谷,图书城,9 光谷,华工,7 图书城,光谷,11 华工,光谷,9 |
起点，终点，权重 |
二、算法实现
算法思想
设G=(V,E)是带权有向图，把顶点集合V分成2组，第1组为已求出最短路径的顶点集合（用S表示），第2组为待定顶点集合（用U表示），按最短路径长度的递增次序依次把U中的顶点加入S中。
算法步骤
（1）初始时，S仅包含1个源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即：U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的边邻接点，则<u,v>权值为∞。
（2）从U中选取1个距离v最小的顶点k，把k加入到S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
三、计算结果报告
输出“武大”到其余各顶点的最短路径。
四、参考答案
4.1 测试数据计算结果
—–最短路径计算结果—
武大, 0
地大, 6
光谷, 10
图书城, 19
华工, 14
程序运行界面如图2所示，显示源数据以及最短路径计算结果。
图2 用户界面示例