下图是一个地区居民点分布的示意图。圆圈表示居民点。为叙述方便，给各居民点编了序号。居民点之间的连线表示连接这两个居民点的道路，连线旁的数字表示道路的长度。现在我们要求从居民点1到居民点8的最短距离。

也许有人会说，这只要把从居民点1到居民点8的所有道路都一一找出，比较各道路的长度就可以找到最短路。

这种方法是解决最短路问题的一种方法，特别是对比较容易列举出所有路的情况是可行的。但是对上述图是否能找到最短路，大家可以试试看。

对于复杂的图或出于想编写程序利用计算机来计算的考虑，需要找到计算最短路的一般算法。下面就结合上面的例子，介绍一种求最短路的算法－狄克斯特拉(Dijkstra)算法。这一算法可求得网络中从一给定点出发到任一点的最短路及其长度。

第一步：首先定义居民点1的永久标号为0，并按下面的方法对每个居民点定义一个临时标号：居民点3、2、4的临时标号分别为居民点1到该居民点的距离2、8、1，其他没有直通居民点1道路的居民点的临时标号都为。

第二步：在所有居民点临时标号中挑选最小者，这里是居民点4的标号1，定义居民点4的永久标号为1。把居民点1涂成黄色，并把居民点1到居民点4的道路涂成红色。永久标号意味着从居民点1到居民点4的最短距离是1。这是因为，从居民点1到居民点4可能还有其他路，但是其他路或要经过居民点2，或要经过居民点3。总之，从居民点1经过其他居民点到居民点4的路必然大于1。

第三步：将已经定义了永久标号的居民点改涂为红色，对应的永久标号改用蓝色表示。再按下面的方法修改除已经定义了永久标号（红圈）外的居民点的临时标号。例如，原本居民点6的标号为，说明从居民点1没有直达居民点1的路。现在由于居民点4已经有了永久标号，居民点1可以通过居民点4到达居民点6。从居民点1到居民点4的最短距离是1，而居民点4到居民点6的距离是9，因而从居民点1到居民点6有一条路的距离是10，于是把居民点6的临时标号由改为10（图10.3中相应的标号用咖啡色标出）。同样，当居民点4定义了永久标号后，居民点1到居民点2增加了一条从经居民点4再到居民点2的路，但是从居民点1经过居民点4再到居民点2的距离与原先居民点2的临时标号一样，所以居民点2的标号不变。重新计算后的各居民点的临时标号在10.3中标出。

接下去就重复第二步到第三步的过程：在图10.3中选最小临时标号值的居民点3（图10.3中的黄色圈）改为永久标号，并把居民点1到居民点3的道路涂成红色，对应的永久标号改用蓝色表示。这样得到图10.3。接下来将居民点3涂为红色，修改除定义了永久标号居民点以外居民点的临时标号，有变动的标号用咖啡色标出，得到图10.4：

再重复上述过程得到的图见图10.5：

接下去的工作我们用“看图识字”的方式列出如下：

最后得到的从居民点1到各居民点的最短路及距离见图10.9所示。特别从居民点1到居民点8的距离为11，最短路是1-3-5-2-6-8，这大约与部分同学一开始尝试的结果不同。

最短路模型不是只能应用到求空间最短路的问题。下面介绍最短路模型在设备更新问题上的应用。

例 某公司使用一种设备, 每年年初需对该设备是否更新作出决策。若换用新设备, 就要支付一笔购置费用；若继续使用原设备, 则要支付一定的维修费:设备使用的年数越长, 年支付的维修费就越高。 各年年初购买新设备的费用及各不同使用年限的年维修费用见下表：（单位：万元）

现在该公司在第一年年初购进了一台新设备，问应如何制定设备更新计划, 使该公司五年内购置新设备的费用和维修旧设备的总费用最少?

解 事实上，设备更新方案是很多的。 例如每年年初均更新设备, 这时五年内购买新设备的费用为11+11+12+12+13=59万元, 而维修费用为5+5+5+5+5=25万元, 总费用59+25=84万元。如果五年内不更新设备, 则其总的费用为11+5+6+8+11+18=59万元。从理论上分析，按是否在第二、第三、第四、第五年购买新设备计算共有种方案。如果穷举各种情况, 显然要化费较多的时间。 为此, 我们用最短路模型来简化问题求解。

以表示第1、2、…,5年的年初。我们把上一年的年末与下一年的年末看作同一时间，,并以表示第五年末，即 也表示第1、2、…,5年的年末。在图上画出六个圈分别表示时间至。从到（）画一个箭头，表示第年年初购买新设备，一直使用到第年的年末的决策。在这个箭头旁标出一个数字，表示这个决策的费用。例如第2年年初买新设备并使用到第四年末，就从到画一个箭头，并在该箭头旁边写上这个决策的费用11+(5+6+8)=30。这样得图10.11。

这样, 一个五年设备更新方案对应一条从到的路，这个方案的总费用就是这条路的总长度。例如第一年、第三年、第五年购买新设备的五年设备更新方案对应这条路，该方案的总费用为22+23+18=63万元。反之，任何一条从到的路对应了一个五年设备更新方案。这样最优的设备更新方案就等价于求从到的最短路。

这个图与本课例子不同，这是“有向图”，即每条边都有一个指定的方向。但就求最短路的方法而言，狄克斯特拉算法仍然适用。

用狄克斯特拉算法求得最短路为或，即第1年、第3年购买新设备, 总费用为53万元；或第1年、第4年购买新设备, 总费用亦为53万元。如果考虑第五年末旧设备可作为二手货出售，则第二种方案更优。