5.3.4 最短路问题的数学模型

最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点 和一个终点 ，求 到 的一条路，使路长最短（即路的各边权数之和最小）。    许多实际问题都归结为最短路问题，例如两地间的管道铺设，线路安装，道路修筑，运路选取等等；再如工厂布局，设备更新等问题也可转化为最短路问题。    这里介绍求最短路的常用算法：    狄克斯屈（ E.D.Dijkstra）双标号法    该法是狄克斯屈在 1959 年提出的，适用于所有权数均为非负（即一切 ， 表示顶点 与 的边的权数）的网络，能够求出网络的任一点 到其它各点的最短路，为目前求这类网络最短路的最好算法。    该法在施行中，对每一个点 都要赋予一个标号，并分为 固定标号 和 临时标号 两种，其含义如下：           ——从始点 到 的最短路长；           ——从始点 到 的最短路长上界。    一个点 的标号只能是上述两种标号之一。若为 标号，则需视情况修改，而一旦成为 标号，就固定不变了。    开始先给始点 标上 标号 0 ，然后检查点 ，对其一切关联边 的终点 ，给出 的 标号 ；再在网络的已有 标号中选取最小者，把它改为 标号。以后每次都检

查刚得到 标号那点，按一定规则修改其一切关联边终点的 标号，再在网络的所有 标号中

选取最小者并把它改为 标号。这样，每次都把一个 标号点改为 标号点，因为网络中总共

有 个结点，故最多只需 次就能把终点 改为 标号。这意味着已求得了 到 的最短路。