Page 208 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

（一）求最短路已有成熟的算法
迪克斯特拉（Dijkstra）算法，其基本思想是按距 u0 从近到远为顺序，依次

求得 u0 到 G 的各顶点的最短路和距离，直至 v0（或直至 G 的所有顶点），算
法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。

代替 l(v) 计算， 把达到这个最小值的一个顶点记为 u i+1 ， 令

若
算法结束时，从 u0 到各顶点 v 的距离由 v 的最后一次的标号 l(v) 给出。在
v 进入 Si 前的标号 l(v) 叫 T 标号，v 进入 Si 时的标号 l(v) 叫 P 标号。算法就是不
断修改顶点的 T 标号，直至获得 P 标号。若在算法运行过程中，将每一顶点获得

P 标号所由来的边在图上标明，则算法结束时，u0 至各项点的最短路也在图上标
示出来了。
例 9 某公司在六个城市 c1，c2 ，…，c6 中有分公司，从 ci 到 c j 的直接航

程票价记在下述矩阵的 (i， j) 下述矩阵的 (i， j) 位置上。（�表示无直接航路），
请帮助该公司设计一张城市 c1 到其他城市间的票价最便宜的路线图。

用矩阵 a nxn （n 为顶点个数）存放各边权的邻接矩阵，行向量 pb 、index1、
index 2 、d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路
的值。其中分量

存放始点到第 i 点最短通路中第 i 顶点前一顶点的序号；

198