經濟管理中一類最短路問題的算法

[摘要] 結合求最小樹的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。用“×”表示去掉某條邊。至此得最短路為:A→B2→C1→D1→E，最短路程為8

例2（TSP問題） 給出距離矩陣，其中每一個元素dij表示到的距離。求從出發，經過各一次，又返回到的最短路和最短路程。

解：首先將該問題化為圖2所示的網絡圖的最短路問題，

圖２

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

僅有一條從v1到v1的路:v1→v3→v4→v2 ，最短路程為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頁