中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

青島仿站定制模板建站武漢seo公司

青島仿站定制模板建站,武漢seo公司,凡科客服,浪琴手表網(wǎng)站建設(shè)圖文章目錄 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ā)…

文章目錄

  • 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);
}
http://www.risenshineclean.com/news/53502.html

相關(guān)文章:

  • 黃埔做網(wǎng)站的公baiduseoguide
  • 企業(yè)站網(wǎng)站建設(shè)優(yōu)化設(shè)計(jì)答案六年級(jí)上冊(cè)語(yǔ)文
  • 網(wǎng)站開(kāi)發(fā)流程管理crm系統(tǒng)網(wǎng)站
  • 北京手機(jī)網(wǎng)站設(shè)計(jì)電話公司網(wǎng)站建設(shè)開(kāi)發(fā)
  • wordpress適合外貿(mào)站seo網(wǎng)絡(luò)培訓(xùn)班
  • 網(wǎng)站qq聯(lián)系怎么做視頻廣告接單平臺(tái)
  • 鄭州網(wǎng)站建設(shè)饣漢獅網(wǎng)絡(luò)千鋒教育北京校區(qū)
  • 官方網(wǎng)站下載打印機(jī)驅(qū)動(dòng)程序手機(jī)百度安裝下載
  • 做網(wǎng)站完整視頻重慶seo博客
  • 直播做愛(ài)網(wǎng)站國(guó)外怎么做信息流廣告代理商
  • 企業(yè)網(wǎng)站建設(shè)的目的和意義seo排名診斷
  • 企業(yè)網(wǎng)站網(wǎng)站建設(shè)電話關(guān)鍵詞優(yōu)化公司如何選擇
  • 2018年的網(wǎng)站制作百度認(rèn)證怎么認(rèn)證
  • 兩學(xué)一做專題教育網(wǎng)站東莞優(yōu)化seo
  • 幫他人做視頻網(wǎng)站違法嗎電子商務(wù)網(wǎng)站建設(shè)教程
  • 邢臺(tái)一天seo西安優(yōu)化排名推廣
  • 聊城網(wǎng)站建設(shè)lcbywlb2b外鏈
  • 公司網(wǎng)站可以自己做永久免費(fèi)的建站系統(tǒng)有哪些
  • 動(dòng)態(tài)網(wǎng)站開(kāi)發(fā)代碼sem代運(yùn)營(yíng)公司
  • 成都網(wǎng)站建設(shè)哪家公司好網(wǎng)絡(luò)營(yíng)銷策劃方案論文
  • 網(wǎng)站開(kāi)發(fā)公司賺錢嗎電腦清理軟件十大排名
  • 海寧高端網(wǎng)站設(shè)計(jì)曼聯(lián)官方發(fā)文
  • 文化傳媒公司網(wǎng)站模板電商營(yíng)銷推廣方法
  • 網(wǎng)站建設(shè)公司做銷售好不好?營(yíng)銷策劃方案ppt
  • 迅速上排名網(wǎng)站優(yōu)化網(wǎng)絡(luò)營(yíng)銷方式有哪些分類
  • 長(zhǎng)寧區(qū)網(wǎng)站建設(shè)設(shè)計(jì)以網(wǎng)絡(luò)營(yíng)銷為主題的論文
  • 北京seo外包公司要靠譜的百度關(guān)鍵詞優(yōu)化師
  • 深圳最新新聞seoul是什么國(guó)家
  • 河南省住房和城鄉(xiāng)建設(shè)廳二維碼網(wǎng)站網(wǎng)站換了域名怎么查
  • 合肥地區(qū)網(wǎng)站制作關(guān)鍵詞優(yōu)化資訊