青島仿站定制模板建站武漢seo公司
文章目錄
- 1. 最短路徑問(wèn)題
- 2. 單源最短路徑--Dijkstra算法
- 算法思想
- 圖解
- 如何存儲(chǔ)路徑及其權(quán)值
- 代碼實(shí)現(xiàn)
- 調(diào)式觀察
- 打印最短路徑
- Dijkstra算法的缺陷
- 3. 源碼
1. 最短路徑問(wèn)題
最短路徑問(wèn)題:
從帶權(quán)有向圖(求最短路徑通常是有向圖)G中的某一頂點(diǎn)出發(fā),找出一條通往另一頂點(diǎn)的最短路徑,最短也就是沿路徑各邊的權(quán)值總和達(dá)到最小。
那下面我們就要來(lái)學(xué)習(xí)幾個(gè)求最短路徑的算法
2. 單源最短路徑–Dijkstra算法
這篇文章我們先來(lái)學(xué)習(xí)第一個(gè)求單源最短路徑的算法——迪杰斯特拉算法(Dijkstra),是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的,然后后面我們還會(huì)學(xué)到求多源最短路徑的算法。
所以這里先給大家介紹一下什么是單源最短路徑,什么是多源最短路徑:
單源最短路徑指的是從一個(gè)源節(jié)點(diǎn)出發(fā),計(jì)算到其他所有節(jié)點(diǎn)的最短路徑。也就是說(shuō),在單源最短路徑問(wèn)題中,只需要確定一個(gè)起點(diǎn),然后計(jì)算該起點(diǎn)到圖中所有其他節(jié)點(diǎn)的最短距離。
多源最短路徑則是在圖中計(jì)算任意兩個(gè)節(jié)點(diǎn)之間的最短路徑。換言之,需要求解所有可能的起點(diǎn)和終點(diǎn)之間的最短路徑。
那下面我們就來(lái)學(xué)習(xí)一下第一個(gè)求單源最短路徑的算法——Dijkstra算法
算法思想
首先我們可以先從概念上了解一下Dijkstra算法的思想:
單源最短路徑問(wèn)題:給定一個(gè)圖G = ( V , E ) ,求源結(jié)點(diǎn)s ∈ V 到圖中每個(gè)結(jié)點(diǎn)v ∈ V的最短路徑。Dijkstra算法就適用于解決帶權(quán)重的有向圖上的單源最短路徑問(wèn)題,同時(shí)算法要求圖中所有邊的權(quán)重非負(fù)。一般在求解最短路徑的時(shí)候都是已知一個(gè)起點(diǎn)和一個(gè)終點(diǎn),所以使用Dijkstra算法求解過(guò)后也就得到了所需起點(diǎn)到終點(diǎn)的最短路徑。
針對(duì)一個(gè)帶權(quán)有向圖G,將所有結(jié)點(diǎn)分為兩組S和Q,S是已經(jīng)確定最短路徑的結(jié)點(diǎn)集合,在初始時(shí)為空(初始時(shí)就可以將源節(jié)點(diǎn)s放入,畢竟源節(jié)點(diǎn)到自己的代價(jià)是0),Q 為其余未確定最短路徑的結(jié)點(diǎn)集合,每次從Q 中找出一個(gè)從起點(diǎn)到該結(jié)點(diǎn)代價(jià)最小的結(jié)點(diǎn)u ,將u 從Q 中移出,并放入S 中,對(duì)u 的每一個(gè)相鄰結(jié)點(diǎn)v (且v不在S中)進(jìn)行松弛操作。松弛即對(duì)每一個(gè)相鄰結(jié)點(diǎn)v ,判斷源節(jié)點(diǎn)s到結(jié)點(diǎn)u 的代價(jià)與u 到v 的代價(jià)之和是否比原來(lái)s 到v 的代價(jià)更小,若代價(jià)比原來(lái)小則要將s 到v 的代價(jià)更新為s 到u 與u 到v 的代價(jià)之和,否則維持原樣。如此一直循環(huán)直至集合Q 為空,即所有節(jié)點(diǎn)都已經(jīng)查找過(guò)一遍并確定了最短路徑,至于一些起點(diǎn)到達(dá)不了的結(jié)點(diǎn)在算法循環(huán)后其代價(jià)仍為初始設(shè)定的值,不發(fā)生變化。
Dijkstra算法每次都是選擇V-S中最小的路徑節(jié)點(diǎn)來(lái)進(jìn)行更新,并加入S中,所以該算法使用的是貪心策略。
Dijkstra算法存在的問(wèn)題是不支持圖中帶負(fù)權(quán)路徑,如果帶有負(fù)權(quán)路徑,則可能會(huì)找不到一些路徑的最短路徑,這個(gè)我們后面也會(huì)給大家演示。
圖解
那只看上面的概念的話,大家可能還不是特別理解,那下面我們來(lái)畫圖帶大家分析一下
首先,我們可以先來(lái)看一下算法導(dǎo)論上給出的圖解:
大家可以自己先看一下
然后,我來(lái)帶大家走一遍這個(gè)過(guò)程:
其實(shí)就按照上面的思想一步步走就行了。
按照上面說(shuō)的,將所有結(jié)點(diǎn)分為兩組S和Q,S是已經(jīng)確定最短路徑的結(jié)點(diǎn)集合,Q 為其余未確定最短路徑的結(jié)點(diǎn)集合。
那起始的時(shí)候,可以認(rèn)為S是空的,所有結(jié)點(diǎn)都在Q里面。
然后這里選擇的起點(diǎn)是s
每次從Q 中找出一個(gè)從起點(diǎn)到該結(jié)點(diǎn)代價(jià)最小的結(jié)點(diǎn)u,那第一次這個(gè)結(jié)點(diǎn)u就是s,可以認(rèn)為s到s的距離是0(圖中每個(gè)結(jié)點(diǎn)里面的值就表示當(dāng)前從起點(diǎn)到自己的最短路徑,還沒(méi)更新的路徑用∞
標(biāo)識(shí)),那把s結(jié)點(diǎn)放到S集合里面,Q中刪去s;
然后對(duì)s 的每一個(gè)相鄰結(jié)點(diǎn)v 進(jìn)行松弛操作(其實(shí)去更新起點(diǎn)到它相鄰點(diǎn)的距離),s到它相鄰的兩個(gè)結(jié)點(diǎn)距離s-t為10,s-y為5,都比原來(lái)從起點(diǎn)到它們的距離小,所以更新
然后再?gòu)腝里面找一個(gè)到起點(diǎn)路徑最短的點(diǎn),那這次找到的是y(此時(shí)s-y為5是最小的),把y從Q中移除,放入S里面;
然后對(duì)y進(jìn)行松弛操作
y相鄰的幾個(gè)頂點(diǎn)到y(tǒng)的距離+y到起點(diǎn)s的距離都比之前起點(diǎn)到它們的距離短,所以都更新
接著繼續(xù)從Q中選一個(gè)到起點(diǎn)距離最短的是z,z從Q中移出,放入S;
接著對(duì)x進(jìn)行松弛操作,更新相應(yīng)的距離
接著繼續(xù)從Q中選一個(gè)到起點(diǎn)距離最短的是t,t從Q中移出,放入S;
接著對(duì)t進(jìn)行松弛操作,更新相應(yīng)的距離
再接著繼續(xù)從Q中選一個(gè)到起點(diǎn)距離最短的是x,x從Q中移出,放入S;
接著再對(duì)x進(jìn)行松弛操作
至此,集合Q 為空(起始Q是滿的,所以n個(gè)結(jié)點(diǎn)的話,其實(shí)就選了n次去更新),即所有節(jié)點(diǎn)都已經(jīng)查找過(guò)一遍并確定了最短路徑
算法執(zhí)行結(jié)束!
如何存儲(chǔ)路徑及其權(quán)值
相信算法現(xiàn)在大家已經(jīng)理解了,但是還有一些問(wèn)題需要我們解決:
既然我們是要求最短路徑,那肯定得把相關(guān)的信息存儲(chǔ)起來(lái)啊,上面圖中直接把每個(gè)頂點(diǎn)對(duì)應(yīng)最短路徑的權(quán)值直接寫到了結(jié)點(diǎn)里面,而且每條路徑是怎么走的,經(jīng)過(guò)了哪些頂點(diǎn),我們也很容易看出來(lái)。
可是后面我們要寫代碼,那在寫代碼的時(shí)候我們?nèi)绾伟堰@些信息也存儲(chǔ)起來(lái)呢?
🆗,是這樣處理的:
因?yàn)槊總€(gè)頂點(diǎn)不是都映射一個(gè)下標(biāo)嘛,所以我們就可以搞一個(gè)數(shù)組,每個(gè)下標(biāo)映射的頂點(diǎn)是誰(shuí),這個(gè)位置就存儲(chǔ)起點(diǎn)到這個(gè)頂點(diǎn)的最短路徑。
那最開(kāi)始就是這樣的:
然后后面我們每次更新最短路徑的時(shí)候修改里面的權(quán)值就行了
那上面存的是最短路徑的權(quán)值,那路徑又要如何存儲(chǔ)呢?
一條路徑可能會(huì)經(jīng)過(guò)多個(gè)頂點(diǎn)啊。
🆗,那這里呢還是用一個(gè)一維數(shù)組就可以搞定:
怎么做呢?
很簡(jiǎn)單,每個(gè)頂點(diǎn)映射的位置存儲(chǔ)路徑上在它前面的那個(gè)頂點(diǎn)映射的下標(biāo),如果把路徑看成一棵樹(shù)的話,就是存儲(chǔ)它的父結(jié)點(diǎn)的下標(biāo)
比如最開(kāi)始就可以這樣存
首先s自己就是起點(diǎn),可以認(rèn)為最短路徑就是s->s,所以它存自己的下標(biāo),然后剩下的頂點(diǎn)都還沒(méi)有更新最短路徑,起始存一個(gè)-1
接著每走一步就去更新數(shù)組就行了(存路徑上它前面的那個(gè)結(jié)點(diǎn)(可以認(rèn)為是它的父結(jié)點(diǎn))的下標(biāo),類似并查集那里用的雙親表示法存儲(chǔ)),那到最后的時(shí)候,就是這樣的
那這樣存儲(chǔ)路徑的話我們想要獲取一個(gè)頂點(diǎn)的最短路徑的時(shí)候,就從這個(gè)頂點(diǎn)開(kāi)始順序它的父親(路徑中的上一個(gè)結(jié)點(diǎn))往上找就行了,找到起點(diǎn)停止,就是一條完整的路徑(類似并查集里面的findRoot順著父結(jié)點(diǎn)向上找根)。
代碼實(shí)現(xiàn)
那下面我們就來(lái)實(shí)現(xiàn)一下代碼:
首先需要給一個(gè)起點(diǎn),然后兩個(gè)vector存儲(chǔ)最短路徑及對(duì)應(yīng)的路徑權(quán)值
然后,按照我們上面分析的思路走就行了
注釋寫的比較清楚,相信大家應(yīng)該很容易可以看懂,說(shuō)一點(diǎn)就是我們現(xiàn)在用的是鄰接矩陣結(jié)構(gòu),所有查找u相鄰的結(jié)點(diǎn)是去鄰接矩陣_matrix
里面找,如果下標(biāo)[u][v]
的位置對(duì)應(yīng)的權(quán)值不是MAX_W
,那它們就相連的,v就是u的一個(gè)相鄰頂點(diǎn),然后再判斷如果源節(jié)點(diǎn)s到結(jié)點(diǎn)u 的代價(jià)與u 到v 的代價(jià)之和(其實(shí)就是距離嘛)是否比原來(lái)s 到v 的代價(jià)更小,若代價(jià)比原來(lái)小則要將s 到v 的代價(jià)更新為s 到u 與u 到v 的代價(jià)之和(更新距離)
調(diào)式觀察
那這就實(shí)現(xiàn)好了,我們可以先通過(guò)調(diào)式觀察一下:
我這里已經(jīng)寫好了一個(gè)測(cè)試用例(最后會(huì)給大家分享源碼),這個(gè)圖就是我們上面講解思想的時(shí)候?qū)?yīng)的那個(gè)圖
我們來(lái)調(diào)式觀察一下
對(duì)比一下我們之前分析的
沒(méi)有問(wèn)題,一模一樣
打印最短路徑
那下面呢我們可以寫一個(gè)大于路徑的函數(shù),把最終得到的起點(diǎn)到各頂點(diǎn)的最短路徑以及權(quán)值都打印出來(lái)看一下,和上面圖上的是否一樣:
那我們拿到這兩個(gè)數(shù)組就可以去打印
但是這里打印的時(shí)候有一個(gè)問(wèn)題:
按我們上面說(shuō)的,找路徑的時(shí)候通過(guò)pPath數(shù)組順著結(jié)點(diǎn)的父親或者說(shuō)它的路徑上的前一個(gè)結(jié)點(diǎn),往上找就行了,找到起點(diǎn)停止。
但是!
這樣找出來(lái)的路徑是不是反的啊,因?yàn)槲覀冏詈笳业降氖瞧瘘c(diǎn),而正常情況應(yīng)該是從起點(diǎn)開(kāi)始嘛。
所以我們要處理一下,也很好搞:
我們可以搞一個(gè)vector把路徑上的結(jié)點(diǎn)保存下來(lái),然后逆置一下,再去打印就行了
來(lái)實(shí)現(xiàn)一下:
然后我們來(lái)打印一下看看:
大家可以對(duì)照一下,沒(méi)有問(wèn)題
Dijkstra算法的缺陷
但是呢,Dijkstra算法是有一些缺陷的,對(duì)于帶有負(fù)權(quán)值的邊的圖,Dijkstra算法是搞不定的!
這里呢也準(zhǔn)備了一個(gè)測(cè)試用例,我們可以來(lái)看一下:
首先它對(duì)應(yīng)的一個(gè)圖應(yīng)該是這樣的:
那我們現(xiàn)在對(duì)這個(gè)圖執(zhí)行Dijkstra算法并打印出來(lái)看一下:
是這樣一個(gè)結(jié)果
但是我們會(huì)發(fā)現(xiàn)如果按照這個(gè)圖有負(fù)權(quán)值的話,其實(shí)有一條最短路徑其實(shí)沒(méi)有更新出來(lái),s->t->y應(yīng)該是3(10+(-7)=3)
也就是說(shuō)3應(yīng)該是起點(diǎn)s到y(tǒng)的最短距離,s->t->y是最短路徑。
圖中帶有負(fù)權(quán)路徑時(shí),貪心策略就失效了。
那為什么會(huì)這樣呢?
因?yàn)榘凑誅ijkstra算法的話
這里起點(diǎn)是s,所以第一次選到s,放到S集合里面,然后對(duì)s的相鄰頂點(diǎn)進(jìn)行松弛操作,更新距離s->t為10,s-y為5,所以第二次選到y(tǒng),那y就被放到S集合里面了,而S是已經(jīng)確定最短路徑的結(jié)點(diǎn)集合,所以它這里的貪心策略就認(rèn)為此時(shí)的5就是s->y的最短路徑距離了(當(dāng)然如果沒(méi)有負(fù)權(quán)值的話這樣是肯定正確的),y的最短路徑已經(jīng)確定了。
所以后面再去對(duì)t的相鄰頂點(diǎn)進(jìn)行松弛的時(shí)候就不會(huì)判斷st+ty的距離是否小于sy,也不會(huì)再更新y的最短路徑了,所以上面s->t->y就沒(méi)有更新出來(lái)。因?yàn)槊看味际菑腝里面選的,而y前面已經(jīng)放到S集合里面了。
但是有了負(fù)權(quán)值的話,sy的最短路徑就不一定是5了(如果全是正的話肯定沒(méi)問(wèn)題),后面繞到其它的路徑如果遇到負(fù)權(quán)值就可能會(huì)比5還小。
所以對(duì)于有負(fù)權(quán)值的圖,Dijkstra算法就不再適用,這種貪心策略就失效了。
那對(duì)于有負(fù)權(quán)值的圖我們?nèi)绾吻笞疃搪窂侥?#xff1f;
bellman—ford算法可以解決負(fù)權(quán)圖的單源最短路徑問(wèn)題
這個(gè)我們下一篇文章就會(huì)講到…
3. 源碼
void Dijkstra(const V& src, vector<int>& pPath, vector<W>& dist)
{//初始化一下記錄路徑和權(quán)值(距離)的數(shù)組size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();pPath.resize(n, -1);dist.resize(n, MAX_W);//集合S為已確定最短路徑的頂點(diǎn)集合,這里我們用一個(gè)數(shù)組表示S集合就可以//,初始化全false(S中無(wú)結(jié)點(diǎn)),表示所有頂點(diǎn)都在Q中,//不在S就在Q(其余未確定最短路徑的結(jié)點(diǎn)集合)vector<bool> s(n, false);pPath[srci] = srci;dist[srci] = 0;//n個(gè)結(jié)點(diǎn),需要選擇n次去更新路徑for (size_t i = 0; i < n; i++){int u = 0;W minDist = MAX_W;//從Q 中找出一個(gè)從起點(diǎn)到該結(jié)點(diǎn)代價(jià)最小的結(jié)點(diǎn)ufor (size_t j = 0; j < n; j++){if (s[i] == false && dist[i] < minDist){u = i;minDist = dist[i];}}//將u 從Q 中移出,并放入S 中s[u] = true;//對(duì)u 的每一個(gè)相鄰結(jié)點(diǎn)v 進(jìn)行松弛操作,如果src->u + u->v < src->v ,就更新距離for (size_t v = 0; v < n; v++){if (s[v] == false && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]){dist[v] = dist[u] + _matrix[u][v];//同時(shí)更新記錄路徑的數(shù)組pPathpPath[v] = u;}}}}void ptintMinPath(const V& src, const vector<int>& pPath, const vector<W>& dist)
{size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();for (size_t i = 0; i < n; i++){if (i != srci)//起點(diǎn)-》起點(diǎn)就沒(méi)必要打印了{//定義一個(gè)vector保存路徑上的結(jié)點(diǎn)vector<int> path;//從當(dāng)前結(jié)點(diǎn)開(kāi)始順著父結(jié)點(diǎn)往上走size_t parenti = i;while (parenti != srci){path.push_back(parenti);parenti = pPath[parenti];}path.push_back(srci);//逆置path數(shù)組reverse(path.begin(), path.end());//打印路徑for (auto e : path){cout << _vertexs[e] << "->";}//打印權(quán)值cout << dist[i] << endl;}}
}
void TestGraphDijkstra()
{/*const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 10);g.AddEdge('s', 'y', 5);g.AddEdge('y', 't', 3);g.AddEdge('y', 'x', 9);g.AddEdge('y', 'z', 2);g.AddEdge('z', 's', 7);g.AddEdge('z', 'x', 6);g.AddEdge('t', 'y', 2);g.AddEdge('t', 'x', 1);g.AddEdge('x', 'z', 4);vector<int> dist;vector<int> pPath;g.Dijkstra('s', dist, pPath);g.ptintMinPath('s', dist, pPath);*/// 圖中帶有負(fù)權(quán)路徑時(shí),貪心策略則失效了。// 測(cè)試結(jié)果可以看到s->t->y之間的最短路徑?jīng)]更新出來(lái)const char* str = "sytx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 10);g.AddEdge('s', 'y', 5);g.AddEdge('t', 'y', -7);g.AddEdge('y', 'x', 3);vector<int> dist;vector<int> pPath;g.Dijkstra('s', dist, pPath);g.ptintMinPath('s', dist, pPath);
}