第十讲    最短路模型

（教材：第十章    最短路模型）

1 2(本页) 3 4

二. Dijkstra 算法

 Dijkstra 算法是一种求最短有向路的方法。

 设 。 Dijkstra 算法基于下面的命题：

假定 是从 到 的最短有向路，则它的一部分（称为子路） 必定是从点 到点 的最短有向路。

 该命题证明

这个命题也可以粗略地表示为：整体最优的决策在局部必然最优的。该思想和动态规划（见教材第十二章）的思想是相同的。

此算法只适用于弧的权 的情况。该算法可以求出从有向网络 中一个给定点出发到任何一个点的最短有向路并求出其长度。

算法中各符号的含义：

:顶点 到  的最短距离，该距离在计算过程中因所取的点增多而不断变化（变小）；

:顶点 到  的最短路上连接  的前面一点的下标。这个下标在计算过程中因所取的点增多而可能会变化；

：以 为出发点，不断地将与 距离最小的点取到集合 内；

: 尚未取入集合 内的点的集合。

Dijkstra 算法过程：

   (1) 给所有的点以临时标号 1，然后以 为出发点，即置

。

   (2) 在中找 ，使得 。置 。

       若 ，进入下一步(3)；若 时，算法终止，此时 即为点 到 的距离， 表示最短路 中与 邻接的点 。

   (3) 对中每一个，如果 ，则 。然后返回步骤(2)。

      〔例1〕 求下图中从 到其他各点的最短有向路。

    解  用Dijkstra算法，计算的迭代过程可列表如下，其中所在的列对应的[ ]中的数字是从 点到 点的最短路的长度； 所在列对应的[ ]中的数字是从 点到 点的最短路中 前一点的下标。

     图示该算法过程

     上述结果可以用下图表示：

    注解2

 1 2(本页) 3 4