實(shí)現(xiàn)Dijkstra算法最短路徑問題詳解

第實(shí)現(xiàn)Dijkstra算法最短路徑問題詳解問題解釋：

從圖中的某個(gè)頂點(diǎn)出發(fā)到達(dá)另外一個(gè)頂點(diǎn)的所經(jīng)過的邊的權(quán)重和最小的一條路徑，稱為最短路徑

解決問題的算法：

迪杰斯特拉算法（Dijkstra算法）

弗洛伊德算法（Floyd算法）

SPFA算法

這篇博客，我們就對(duì)Dijkstra算法來做一個(gè)詳細(xì)的介紹

2、Dijkstra算法介紹

算法特點(diǎn)：

迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑問題，算法最終得到一個(gè)最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。

算法的思路

Dijkstra算法采用的是一種貪心的策略，聲明一個(gè)數(shù)組dis來保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合：T，初始時(shí)，原點(diǎn)s的路徑權(quán)重被賦為0（dis[s]=0）。若對(duì)于頂點(diǎn)s存在能直接到達(dá)的邊（s,m），則把dis[m]設(shè)為w（s,m）,同時(shí)把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長度設(shè)為無窮大。初始時(shí)，集合T只有頂點(diǎn)s。然后，從dis數(shù)組選擇最小值，則該值就是源點(diǎn)s到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T中，OK，此時(shí)完成一個(gè)頂點(diǎn)，

然后，我們需要看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在dis中的值。

然后，又從dis中找出最小值，重復(fù)上述動(dòng)作，直到T中包含了圖的所有頂點(diǎn)。

3、Dijkstra算法示例演示

下面我求下圖，從頂點(diǎn)v1到其他各個(gè)頂點(diǎn)的最短路徑

首先第一步，我們先聲明一個(gè)dis數(shù)組，該數(shù)組初始化的值為：

我們的頂點(diǎn)集T的初始化為：T={v1}

既然是求v1頂點(diǎn)到其余各個(gè)頂點(diǎn)的最短路程，那就先找一個(gè)離1號(hào)頂點(diǎn)最近的頂點(diǎn)。通過數(shù)組dis可知當(dāng)前離v1頂點(diǎn)最近是v3頂點(diǎn)。當(dāng)選擇了2號(hào)頂點(diǎn)后，dis[2]（下標(biāo)從0開始）的值就已經(jīng)從“估計(jì)值”變?yōu)榱恕按_定值”，即v1頂點(diǎn)到v3頂點(diǎn)的最短路程就是當(dāng)前dis[2]值。將V3加入到T中。

為什么呢？因?yàn)槟壳半xv1頂點(diǎn)最近的是v3頂點(diǎn)，并且這個(gè)圖所有的邊都是正數(shù)，那么肯定不可能通過第三個(gè)頂點(diǎn)中轉(zhuǎn)，使得v1頂點(diǎn)到v3頂點(diǎn)的路程進(jìn)一步縮短了。因?yàn)関1頂點(diǎn)到其它頂點(diǎn)的路程肯定沒有v1到v3頂點(diǎn)短.

OK，既然確定了一個(gè)頂點(diǎn)的最短路徑，下面我們就要根據(jù)這個(gè)新入的頂點(diǎn)V3會(huì)有出度，發(fā)現(xiàn)以v3為弧尾的有：v3,v4,那么我們看看路徑：v1–v3–v4的長度是否比v1–v4短，其實(shí)這個(gè)已經(jīng)是很明顯的了，因?yàn)閐is[3]代表的就是v1–v4的長度為無窮大，而v1–v3–v4的長度為：10+50=60，所以更新dis[3]的值,得到如下結(jié)果：

因此dis[3]要更新為60。這個(gè)過程有個(gè)專業(yè)術(shù)語叫做“松弛”。即v1頂點(diǎn)到v4頂點(diǎn)的路程即dis[3]，通過v3,v4這條邊松弛成功。這便是Dijkstra算法的主要思想：通過“邊”來松弛v1頂點(diǎn)到其余各個(gè)頂點(diǎn)的路程。

然后，我們又從除dis[2]和dis[0]外的其他值中尋找最小值，發(fā)現(xiàn)dis[4]的值最小，通過之前是解釋的原理，可以知道v1到v5的最短距離就是dis[4]的值，然后，我們把v5加入到集合T中，然后，考慮v5的出度是否會(huì)影響我們的數(shù)組dis的值，v5有兩條出度：v5,v4和v5,v6,然后我們發(fā)現(xiàn)：v1–v5–v4的長度為：50，而dis[3]的值為60，所以我們要更新dis[3]的值.另外，v1-v5-v6的長度為：90，而dis[5]為100，所以我們需要更新dis[5]的值。更新后的dis數(shù)組如下圖：

然后，繼續(xù)從dis中選擇未確定的頂點(diǎn)的值中選擇一個(gè)最小的值，發(fā)現(xiàn)dis[3]的值是最小的，所以把v4加入到集合T中，此時(shí)集合T={v1,v3,v5,v4},然后，考慮v4的出度是否會(huì)影響我們的數(shù)組dis的值，v4有一條出度：v4,v6,然后我們發(fā)現(xiàn)：v1–v5–v4–v6的長度為：60，而dis[5]的值為90，所以我們要更新dis[5]的值，更新后的dis數(shù)組如下圖：

然后，我們使用同樣原理，分別確定了v6和v2的最短路徑，最后dis的數(shù)組的值如下：

因此，從圖中，我們可以發(fā)現(xiàn)v1-v2的值為：∞，代表沒有路徑從v1到達(dá)v2。所以我們得到的最后的結(jié)果為：

起點(diǎn)終點(diǎn)最短路徑長度

v1v2無∞

v3{v1,v3}1