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);
}