兩類經(jīng)典算法求最短路問(wèn)題剖析

韋艷肖

摘 要：舉例說(shuō)明Dijkstra算法和Floyd算法求最短路問(wèn)題，通過(guò)規(guī)定起點(diǎn)、終點(diǎn)、各點(diǎn)之間權(quán)值的大小，找出了最短路徑，求出最短路長(zhǎng)，并增加負(fù)權(quán)值、方向和閉合回路來(lái)分別研究?jī)煞N算法在運(yùn)算中的利弊以及適用性。

關(guān)鍵詞：Dijkstra算法；Floyd算法；最短路

1.引言

眾所周知，最短路算法有兩種基本算法，一是指定的頂點(diǎn)之間的最短路徑算法，二是所有頂點(diǎn)之間的最短路算法，其中所有頂點(diǎn)間最短路算法更具有代表性。目前，求最短路問(wèn)題的方法很多，各有優(yōu)劣性，而實(shí)際應(yīng)用中以兩類經(jīng)典算法居多，分別是1959年E.W.Dijkstra提出的Dijkstra算法和1962年Floyd提出的Floyd算法。

1.1 Dijkstra算法

Dijkstra算法的基本思想是：若起點(diǎn)vs到終點(diǎn)vt的最短路經(jīng)過(guò)點(diǎn)v1，v2，v3，則v1到vt的最短路是p1t={v1，v2，v3，vt}，v2到vt的最短路是p2t={v2，v3，vt}，v3到vt的最短路是p3t={v3，vt}，Dijkstra算法是在圖上進(jìn)行一種標(biāo)號(hào)迭代的過(guò)程。不妨設(shè)?。╥，j）的長(zhǎng)度為cij≥0，vi到vj的最短路記為pij，最短路長(zhǎng)記為L(zhǎng)ij。Dijkstra算法的基本步驟如下[1-2]：

（1）找出所有起點(diǎn)vi已標(biāo)號(hào)，終點(diǎn)vj未標(biāo)號(hào)的弧，集合為B={（i，j）︱vi已標(biāo)號(hào)；vj未標(biāo)號(hào)}，如果這樣的弧不存在或已標(biāo)號(hào)則計(jì)算結(jié)束。

（2）計(jì)算集合B中弧的標(biāo)號(hào)：k（i，j）=b（i）+cij。

（3）b（l）=minj{k（i，j）|（i，j）∈B}，在弧的終點(diǎn)vl標(biāo)號(hào)b（l），返回步驟（1）。

完成步驟（1）～（3）為一輪計(jì)算，每一輪計(jì)算至少得到一個(gè)點(diǎn)的標(biāo)號(hào)，最多通過(guò)n輪計(jì)算得到最短路。

1.2 Floyd算法

Floyd算法是一種矩陣迭代方法，也是一種表格迭代方法，對(duì)于求任意點(diǎn)間最短路、混合圖的最短路、有負(fù)權(quán)圖的最短路等一般網(wǎng)絡(luò)問(wèn)題來(lái)說(shuō)是比較有效的，F(xiàn)loyd算法的基本步驟如下[1-2]：

（1）寫出vi一步到達(dá)vj的距離矩陣L1=（L（1）ij），L1也是一步到達(dá)的最短距離矩陣。如果vi 與vj之間沒(méi)有關(guān)聯(lián)，則令cij=+∞。

（2）計(jì)算兩步最短矩陣。設(shè)vi到vj經(jīng)過(guò)一個(gè)中心點(diǎn)vr，要兩步到達(dá)vj，則vi到vj的最短距離為L(zhǎng)（2）ij=minr{cir+crj}，最短距離矩陣為L(zhǎng)2=（L（2）ij）。

（3）計(jì)算k步最短距離矩陣。設(shè)vi經(jīng)過(guò)中間點(diǎn)vr到達(dá)vj，vi經(jīng)過(guò)k-1步到達(dá)點(diǎn)vr的最短距離為L(zhǎng)（k-1）ir，vr經(jīng)過(guò)k-1步到達(dá)點(diǎn)vj的最短距離為L(zhǎng)（k-1）rj，則vi經(jīng)k步到達(dá)vj的最短距離為L(zhǎng)（k）ij=minr{L（k-1）ir+L（k-1）rj}，最短距離矩陣為L(zhǎng)k=（L（k）ij）。

（4）比較矩陣Lk與Lk-1，當(dāng)LK=Lk-1時(shí)得到任意兩點(diǎn)間的最短距離矩陣Lk。

2.具體應(yīng)用

本節(jié)中通過(guò)具體例子，如圖1，圖2所示，利用Dijkstra算法和Floyd算法分別求出頂點(diǎn)v1到頂點(diǎn)v8的最短路以及最短路長(zhǎng)。

即得出v1到v8的最短距離為18，其所對(duì)應(yīng)的最小生成樹和最短路線圖分別如圖2-8和2-9所示：

3.算法分析

綜上，通過(guò)具體例子介紹和分析了Dijkstra算法和Floyd算法這兩種非常經(jīng)典的最短路算法。可得Dijkstra算法是主要用于解決無(wú)負(fù)權(quán)值的有向圖和無(wú)向圖的最短路算法，F(xiàn)loyd算法是通過(guò)矩陣運(yùn)算來(lái)求解網(wǎng)絡(luò)中的最短路問(wèn)題的方法。這兩種算法都可計(jì)算一個(gè)結(jié)點(diǎn)到其它結(jié)點(diǎn)的最短路徑。Dijkstra算法是運(yùn)用表上做圖的方式一個(gè)一個(gè)點(diǎn)的添加，根據(jù)最小的權(quán)值的選擇依次對(duì)各點(diǎn)進(jìn)行標(biāo)號(hào)，直到將所有的點(diǎn)都標(biāo)上號(hào)，從而找出最短路徑。而Floyd算法是首先將所有的點(diǎn)都標(biāo)出，將各點(diǎn)間的權(quán)值反應(yīng)在矩陣上，再用矩陣計(jì)算出最優(yōu)矩陣。Dijkstra算法的優(yōu)點(diǎn)是算法比較簡(jiǎn)單明了，不易出錯(cuò)，但是也有缺點(diǎn)，主要是步驟卻非常繁瑣。Floyd算法的算法雖然說(shuō)有點(diǎn)復(fù)雜，但是效率比較高，在計(jì)算時(shí)能夠節(jié)約時(shí)間。綜上所述，兩種算法的差別很大，但是效果卻是相同的。我們?cè)趯?shí)際的運(yùn)用中可以按各自的需求選擇合適的方法。（作者單位：河池學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院）

基金項(xiàng)目：廣西高?？茖W(xué)研究項(xiàng)目（201010LX481），廣西高等教育教學(xué)改革工程項(xiàng)目（2015JGA552）

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）[M].北京：清華大學(xué)大學(xué)出版社，2007.

[2] 王桂平.王衍.任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京：北京大學(xué)出版，2011.

[3] 王朝瑞.圖論[M].北京：北京理工大學(xué)出版社，2002.

[4] 嚴(yán)寒冰等.基于GIS的城市道路網(wǎng)最短路徑算法探討.計(jì)算機(jī)學(xué)報(bào)，2000，23（2）：210-215.

[5] 徐鳳生.最短路徑的求解算法[J].計(jì)算機(jī)應(yīng)用，2004，24（5）：88- 89.

[6] 張新元.最短路問(wèn)題的Seidel迭代[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，1993，7（2）：18-21.

[7] 林華珍，周根貴.求解最短路問(wèn)題的一種優(yōu)化矩陣算法[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，4（4）：14-16.