第三节最短路问题

最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。这里所说的距离只是权数的代称，在实际问题中，权数可以是时间、费用等。最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题。

最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法。另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。

5.3.1有向图的狄克斯屈拉(Dijkstra)标号算法

先求有向图的最短路，设网络图的起点是，终点是，以为起点为终点的弧记为，距离为。有向图的狄克斯屈拉(Dijkstra)标号算法涉及到两个标号，点标号：—起点到点的最短路长；边标号：=+。

求从某一点s到另一点的最短路的具体步骤为：

(1)令起点的标号；＝0。

(2)找出所有已标号未标号的弧集合B={}，如果这样的弧不存在或已标号则计算结束；

(3)计算集合中弧长=+，选一个点标号={|∈}，

(4)重复第三步，一直到点得到标号为止。

【例5.3】用Dijkstra标号算法求下面5-8中点①到点⑦的最短路

图5-8

解：第一轮，给标号为0，就是已标号的点，以为起点的弧有，，，注意到的弧长最小，故给标号小方框6，则变成标号点。

第二轮，以，为起点的弧有，，，经计算，与弧长的和最短为9，则在标号小方框9，变成已标号点。

如此继续下去，得到了图5-7各点的标号，标注在点旁小方框内。到的最短路为：=｛，，，，｝，最短路长为=29。

从上例知，只要某点已标号，说明已找到起点到该点的最短路线及最短距离，因此可以将每个点标号，求出到任意点的最短路线，如果某个点不能标号，说明不可达。最短路线可能不唯一，但最短路长唯一；Dijkstra标号算法条件是弧长非负，而且是求最小值问题，最大值问题无效。

5.3.2无向图最短路的求法

如果与之间有一条无方向的边关联，说明与两点之间可以互达，当与之间至少有两条边关联时，留下最短边，去点其他关联边，对于无向图最短路Dijkstra标号算法照样有效。具体方法为：无向Dijkstra标号算法图最短路的求法只将上述步骤(2)改动一下即可。点标号：—起点到点的最短路长边标号：=+。

(2)找出所有一端已标号另一端未标号的边集合={}如果这样的边不存在或已标号则计算结束；点标号与边标号的计算公式同有向图。

【例5.4】求图5-9中到的最短路

解：

(1)从点出发，对标号，令标号为0，标注在其旁边的小方框内，见图5-9。

(2)同相邻的未标号点为，，而{()，()}=()，所以对标号，其大小B(3)标注在小方框内，见图5-10。

(3)同已标号点，相邻而未标号的点为，，，注意到()=5，()=()+()=9，()=()+ ()=6，所以给，大小为5，标注在小方框内，见图5-11。

重复上述过程，最后得到了标号为10，这样就求得了从到各点的最短距离。见图5-12，其中粗线表示从到各点的最短路。

5.3.3最短路的Floyd算法

Dijkstra标号算法提供了从网络图中某一点到其它点的最短距离，但实际问题有时是求任意两点之间的最短距离，而且有时网络图带有多重边、权是负数的情形，此时使用Dijkstra标号算法就显得不恰当。Floyd算法提供了具体的解法。

Floyd算法基本步骤：

(1)写出一步到达的距离矩阵，也是一步到达的最短距离矩阵。如果与之间没有边关联，则令=+

(2)计算二步最短距离矩阵。设到经过一个中间点两步到达，则到的最短距离为，最短距离矩阵记为。

(3)计算步最短距离矩阵。设经过中间点到达，经过步到达点的最短距离为，经过步到达点的最短距离为，则经步到达的最短距离为，最短距离矩阵记为。

(4)比较矩阵与，当＝时得到任意两点间的最短距离矩阵。

设图的点数为并且≥0，迭代次数由式(5-1)估计得到

                                    (5-1)

【例5.5】图5-13是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。

解：(1)依据图5-13，写出任意两点间距离表，见表5-2。本例=8，按公式(5-1)，可算得只需计算到即可。

(2)根据算法的第二步，可计算得到两步距离矩阵，见表5-3。

(3)由第三步的计算方法，可得表5-4，由表5-4任意两个城市之间的最短距离。

表5-2 最短距离表

表5-3 最短距离表

计算说明：等于表5-3中第行与第列对应元素相加取最小值

=5

表5-4最短距离表

表5-4计算示例：等于表5-3中第行与第列对应元素相加取最小值。例如，经过三步(最多三个中间点4条边)到达的最短距离是：

表5-4就是最优表，从表中可以得出任意两点间的距离。

5.3.4应用举例

【例5.6】设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的还是使用旧的，若购置新的，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年内的设备更新计划，使得总的支付费用最小。现在考虑一个五年计划，若已知该种设备在各年年初价格见表5-5(万元)。

表5-5 年初价格

还已知使用不同时间(年)的设备所需要的维修费用见见表5-6(万元)。

表5-6 维修费用

解：用点代表“第年年初购进一台新设备”这种状态(加设一点，理解为第5年年底)。从到，…，各画一条弧，弧(，)表示在第年年初购进的设备一直使用到第年年初，即第年底。每一条弧的权可根据资料计算出来，如(，)是第一年初购进一台新设备，一直使用到第4年底的费用(购置费11万，维修费5+6+8+11，一共41万)，这样就得到图5-14。

这样就将制定设备更新计划问题转化为求有向图的最短路问题，利用标号法可得：{，，}及{，，}均为最短路，即有两个最优方案，第一个是第1年，第3年各购置一台新设备，另一方案是第1年，第4年购置新设备，五年总的支付费用均为53万元。