7.7.1　求某一顶点到其他各顶点的最短路径

设有带权的有向图D＝（V，｛E｝），D中的边权为W（e）。已知源点为v0，求v0到其他各顶点的最短路径。例如，在图7－33（a）所示的带权有向图中，v0为源点，则v0到其他各顶点的最短路径如图7－33（b）所示，其中各最短路径按路径长度从小到大的顺序排列。

图7－33 最短路径

求解单源最短路径的经典算法是Dijkstra算法。

1.基本思想

设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V－S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，…，vk，就将vk加入集合S中，并将路径v，…，vk，vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。

下一条最短路径（设其终点为vi）或者是弧（v0，vi），或者是中间经过S中的顶点而最后到达顶点vi的路径。

2.算法示例

算法示例如图7－34所示。

3.算法步骤

（1）令S＝｛Vs｝，用带权的邻接矩阵表示有向图，对图中每个顶点vi按以下原则置初值：

（2）选择一个顶点vj，使得：dist［j］＝Min｛dist［k］｜vk∈V－S｝，vj就是求得的下一条最短路径终点，将vj并入S中，即S＝S∪｛vj｝。

（3）对V－S中的每个顶点vk，修改dist［k］，方法是：若dist［j］＋Wjk＜dist［k］，则修改为：

（4）重复（2）和（3），直到S＝V为止。

图7－34 最短路径算法图例

4.算法实现

求最短路径的算法描述如下。

算法7.10 图的最短路径算法

显然，算法的时间复杂度为O（n2）。