。
为了进行网络最短路径分析，需要将网络转换成有向图。无论是计算
? 183 ?最短路径还是最佳路径，其算法都是一致的，不同之处在于有向图中每条
弧的权值设置。如果要计算最短路径，则权重设置为两个节点的实际距
离；而要计算最佳路径，则可以将权值设置为从起点到终点的时间或费
用。Dijkstra算法可以用于计算从有向图中任意一个节点到其他节点的最
短路径。下面是该算法的描述：
（1）用带权的邻接矩阵 Cost来表示带权的n个节点的有向图，
Cost[i，j]表示弧＜vi，vj＞的权值，如果从vi 到vj 不连通，则Cost[i，j]=
∞。图3-3-11表示了一个带权有向图以及其邻接矩阵。
图3-3-11 带权的有向图和邻接矩阵
然后，引进一个辅助向量 Dist，每个分量 Dist[i]表示从起始点到每
个终点vi的最短路径长度。假定起始点在有向图中的序号为i0，并设定该
向量的初始值为：
Dist[i]=Cost[i0，i] vi ∈V
令S为已经找到的从起点出发的最短路径的终点的集合。
（2）选择vj，使得
Dist[j]= Min{Dist[i]|Vi ∈ V—S} vi ∈V
vj就是当前求得的一条从vi0出发的最短路径的终点，令
S=S∪ {vj}
（3）修改从vi0出发到集合V—S中任意一顶点vk 的最短路径长度。如
果
Dist[j]+Cost[j，k]＜Dist[k]
则修改Dist[k]为：Dist[k]=Dist[j]+Cost[j，k]
（4）重复第2、3步操作共n—1次，由此求得从vi0出发的到图上各个
顶点的最短路径是依路径长度递增的序列。表3-3-3是图3-3-11根据
? 283 ?Dijkstra计算的结果。
表3-3-3 用Dijkstra计算的结果
终点 从v0到其他各个节点的最短路径