经济管理中一类最短路问题的算法

[摘要] 结合求最小树的Kruskal算法和破圈运算，给出求一类最短路问题的一种简单算法。

[关键词] 最短路问题Kruskal算法破圈运算

引言

最短路问题是经济管理中经常遇到的问题，如煤气管道铺设就是其中的一类，我们把它归结为图1所表示的网络，联结各点的线段上的数字表示它们之间的弧长。求A点到E点的最短路和最短路程。

图1

类似这样的问题我们称之为最短路问题，它显然是一个多阶段决策问题。[1]、[2]、[3]均给出了递推法，并由此导出动态规划最优化原理。[4]中对递推法做出改进，引入摹矩阵及其运算，得出摹矩阵表上作业法，该方法简洁明了且易于操作，但在算法复杂性上没有得到改善。本文给出一种类似于Kruskal求最小树的方法来求上述最短路问题，并用以解决小型旅行售货员问题(TSP问题)。

一、算法思想

设图G有m条边和n个顶点，求其最小树的Kruskal算法的基本思路是从图G的所有m条边中选取n-1条权尽量小的边，并且使得不构成回路，从而得到最小树。受此启发，我们也可在类似于图1的网络中，将所有的边按权的大小从小到大排列并标号，权相同的边排在一起。权最小的边标为1号，权次小的边标为2号，依次标为3号、4号、…

(1)先选取1号边(可能有多条)，若这些边构成了从A 点到E点的路，不管有一条还是多条，任取一条必是最短路。

(2)另外的情况就是，这些权最小的边不能构成从A 点到E点的路，则再选取2号边，和1号边一起，我们再来考察这些边是否构成从A 点到E点的路。若仅有一条，则必是最短路；若不只一条，则在不考虑有向边的方向的前提下，图中必有圈存在，这时我们采用破圈法：任取一个圈，去掉圈中权最大的边(若权最大的边不只一条，则任意去掉一条)，相应地就去掉了权和较大的那条路，若还有圈，则依此法类推，直到只剩下一条路，必是最短路。

(3)若在(2)中所取的边仍不能构成从A 点到E点的路，则再选取3号边，和前面所取的边一起，重复(2)的工作。因为所给图中边数有限，所以此算法必在有限步后终止。

二、算法步骤

第一步 开始把边按权的大小从小到大排列并标号：权最小的边标为1号，权次小的边标为2号，依此类推，将剩余的边分别标为3号、4号、…（权相同的边标号相同）置i;=1

第二步 选取i号边，考察从A 点到E点是否存在路；

第三步 若没有路，置i:=i+1，转第一步；否则，转第四步；

第四步 若仅有一条路，停止。这条路即为所求；否则，转第五步；

第五步 破除所有的圈，转第四步；

三、算例

例1 求图1中从A点到E点的最短路和最短路程。

解:

说明:在圈AB1C2B2A中，去掉最长边AB1;在圈AB2C1B3中，去掉最长边B3C1;在圈B2C1D1C2B2中，去掉最长边B2C2。用“×”表示去掉某条边。至此得最短路为:AB2C1D1E，最短路程为8

例2（TSP问题） 给出距离矩阵，其中每一个元素dij表示到的距离。求从出发，经过各一次，又返回到的最短路和最短路程。

解：首先将该问题化为图2所示的网络图的最短路问题，

图２

利用本文给出的算法求解如下：

仅有一条从v1到v1的路:v1v3v4v2 ，最短路程为23。

结束语

例1和例2均选自[1]，按照[1]所使用的递推法，解例1要做15次加法运算,以及8次比较运算，而用本文所给算法只需3次迭代，3次破圈运算。同样用递推法解例2要做15次加法运算,以及5次比较运算，而用本文所给算法只需2次迭代即可。由此可见，本文所给算法在算法复杂性上比递推法要好，而且简单易懂，也便于计算机编程实现。对于大规模的上述最短路问题，更显示出其优越性。

参考文献：

[1]刁在筠郑汉鼎刘家壮等:运筹学[M]北京:高等教育出版社2001年9月第1版第180页、第155～158页、第160页

[2]教材编写组运筹学(修订版)[M]北京:清华大学出版社.1990年1月第2版，第199～200页

[3]胡运权:运筹学教程[M].北京：清华大学出版社,2003年5月第2版,第206～207页

[4]秦裕瑗秦明复:运筹学简明教程[M].北京:高等教育出版社、海得堡：施普林格出社,2000年10月第1版,第86～88页