基于輔助圖最短路算法的程序設計及應用

高 燕

(河北省高速公路青銀管理處)

自1962年提出求解網絡最大流的第一算法—標號法以來，不少學者開始應用數學網絡理論對路網系統進行研究并提出計算路網容量的模擬方法和數學模型，近幾年，對于路網容量的研究得到很大進展，最大流理論也有所應用。但是以往應用最大流理論對路網容量的計算方法在對路網簡化和計算量上各有缺陷，不方便應用到計算機程序設計中。因此從另一個角度入手，尋找一種更適合于編程計算的最大流最小割算法。利用基于輔助圖的最短路算法來代替最大流最小割算法就是一個很好的途徑，輔助圖最短路算法適應于單起終點的無向網絡，可以應用到可平面化的道路網絡中，不僅可以簡單處理路網，而且該算法能夠輸出確定的網絡中任意兩個節點之間的流量值。

1 對路網的抽象簡化

第一，路網應該簡化為無向網絡更為合理，因為在道路網絡中，每個路段一般都是雙向的，即使有單向街道也往往在很接近的地方有對向的平行街道與之相匹配。以往的輔助圖最短路算法從理論上提出了路網應該簡化為無向網絡，但是在實例處理時體現不夠，即一般來講基于此，提出對無向網絡進行測算的方法。

第二，無向圖的可行流，大多表現在多收發點的多種物流上。以往算法大都將其簡化到確定的幾個網絡節點上，即車站、碼頭和機場等重要的交通集散點。雖然這種簡化有一定的合理性，但是這樣找到的最短路可能不是整個網絡中的最短路，即可能存在非收發點之間的最短路，其值小于收發點之間的最短路的值。通過對算法輸出進行改進，將輔助路網內部任意兩個節點之間的最短路徑，即原路網任意兩個節點之間的最大流輸出并進行分析。

2 對最短路算法的改進

利用以上算法，首先將現狀路網轉化成可以利用最短路算法求解最小割的路網模式，包含收發點選取、邊權賦值、構造輔助路網等，應用Matlab 軟件，選取Dijkstra 算法對最短路徑部分進行計算機編程。本算法不但應用先進的軟件工具進行編程，而且對程序輸出顯示進行改進，可以輸出輔助路網中任意兩點的最短路徑和最大流量，程序的算法流程圖見圖1。

3 算法實例

如圖2 所示，該通道網絡的起點為v1，終點為v6，通道的通行能力用標注在路線旁邊的數字表示。下面以圖2 為例，給出本算法的應用過程。

圖1 算法流程圖

圖2 通道網絡簡化圖

下面開始構造該網絡的輔助圖，如圖3 所示，G 中存在多少個內面，G*就可以產生多少個中間點與之對應;另外，G*的起點和終點位于G 的上面和下面。輔助圖中各邊的權值與原路網中與之相交的G 中的邊權一一對應。

圖3 輔助路網圖

根據以上兩圖寫出輔助圖路網的路線權值矩陣，這個矩陣不但可以表示輔助圖當中各個節點的連通狀況，而且能表示各條路線的通行能力。兩點之間沒有直接通路的路線權值應該無限大，即無路可走，這里根據實際情況用一個較大的數表示，該路網選取100(遠遠大于有連接通路的其它節點之間的權值即可)。矩陣如下

將初始矩陣讀入計算機程序當中，利用Matlab 軟件程序可以計算出路網最大流量矩陣和路網中任意兩點之間的最短路徑。

最大流量矩陣如下

從路網容量矩陣可以看出，原路網的最大流量為M16=9，即原通道網絡圖中從v1到v6的最大流量為9。另外該矩陣還輸出任意兩點之間的最大流Mij，除了始、終結點之間的容量外，其它內部結點之間的路網容量雖然不符合路網容量的定義，但是能夠反映路網中內部流量情況。

最短路矩陣Rij記錄從點到點的最短路徑的中間結點，該路網最短路矩陣具體如下

最短路徑確定方法為

由此可以看出，輔助圖G*的最短路是1.5.6，最短路的值為9。與之相對應的原路網的最小割集是(v3v6、v5v6)，最小割集容量是9。

4 小 結

在已有算法的基礎上，通過改進得到了求無向路網中所有最小割集的較為簡便的算法，通過構造輔助路網并求其最短路，利用Matlab 計算機語言程序實現該算法，并且可以根據需求輸出輔助網絡中任意兩點間的最短路和原路網任意兩點的最大流，不但減少了計算量，而且提高了該算法應用于計算機上的可靠性。將該算法應用于可平面化的實際路網中，可以快速找到路網的關鍵斷面，即運輸通道的瓶頸，為路網規劃和改建擴建提供理論依據。

［1］楊濤，徐吉謙. 運輸網絡極大流的一種新算法［J］. 土木工程學報，1991，24(2).

［2］陳春妹.路網容量研究［D］.北京工業大學，2002.

［3］楊曉萍.基于網絡最大流理論的城市道路網容量研究［D］. 哈爾濱工業大學，2004.