§ 3最短路问题
在实践中常遇到的一类网络问题是最短路问题。

给定一个有向赋权图D=（V，A），对每一个弧a =（ ,），相应有权≥0，指定D中的为发点，为终点。

最短路问题就是要在所有到的路中，求出一条总权数最小的路。

这里权数可以是距离，也可以是时间，或者是费用等等。

最短路问题是最重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它优化问题。

3.1 狄克斯拉（Dijkstra）算法
最短路问题可以化为线性规划问题求解，也可以用动态规划方法求解，这里介绍一种有效算法—狄克斯拉（Dijkstra）算法，这一算法是1959年首次被提出来的。

该算法适用于每条弧的权数≥0情形。

算法的基本思路：从发点出发，有一个假想的流沿网络一切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向继续前进，则最先到达终点的流所走过的路径一定是最短的。

为了实现这一想法，对假想流依次到达的点，依次给予p标号，表示到这些点的最短距离。

对于假想流尚未到达的点给予T标号，表示到这些点的最短距离的估计值。

具体作法如下：
1°标p（）=0，其余点标T（）=+∞;
2°由刚刚获得p标号的点出发，改善它的相邻点的T标号,即
新的T（）=min{老的T（），p（）+ }
若T（）= p（）+ ωij ，则记k（）=（前点标记）;
3°找出具有最小T标号的点，将其标号改为p标号。

若已获得p标号，则已找到最短路，由k （）反向追踪，就可找出到的最短路径，p（）就是到的最短距离。

否则，转2°。

例2 求图下中v1 到v8 的最短路。

解：标p（）=0，其余点标
将具有最小T标号的点的标号改为p标号：p（）=3；
目前，点具有最小T标号，将其标号改为p标号： p（）=4；
目前，点具有最小T标号，将其标号改为p标号： p（）=5；
目前，点具有最小T标号，将其标号改为p标号： p（）=6；
目前，点具有最小T标号，将其标号改为p标号：
最短路径为：
因p（）=12，所以→的最短距离为12。

最短路问题不仅可以求解交通图中两点之间的最短距离，实际中很多问题也可变为最短路问题加以求解。

例如设备更新问题，厂区合理布局问题等。

兹举一例：
例3（设备更新问题）某企业使用一台设备，在每年年底，企业都要决策下年度是购买一台新设备呢？还是继续使用这台设备。

若购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修费，而维修费随着设备的使用年限延长而增加。

现根据以往统计资料已经估算出设备在各年初的价格和不同使用年限的修理费用，分别如表7-1、表7-2所示。

试确定一个五年内的设备更新计划，使五年内总支出最小。

3.2 图上标示法
下面我们结合例3介绍求解最短路问题的图上标示法，它比狄克斯拉算法更简洁。

解：先根据表7-1、表7-2的数据画出设备更新费用网络图，如图7-14所示。

图中点表示第i 年开始，弧（ ,）表示设备第i 年初使用到第j 年初，弧（ ,）上的权数表示该期间设备所需的费用。

这样，求五年内设备最优更新方案便转化为求→的最短路。

设d（）表示点到终点的最短距离，根据动态规划最优性原理，最短路径中任何子路径也必然是最短的。

因此有
注意，上式要对以为起点的所有弧（ ,）进行计算。

然后将计
算结果直接标在图中点的旁边，同时标出与点最近的邻接点。

先从点算起，逆向进行。