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

[摘要] 結合求最小樹的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點的路。若僅有一條，則必是最短路；……