柚子快報(bào)激活碼778899分享：c++ 【圖論】迪杰特斯拉算法

http://yzkb.51969.com/

文章目錄

迪杰特斯拉算法主要特點(diǎn)基本思想算法步驟示例

實(shí)現(xiàn)迪杰斯特拉算法基本步驟算法思路

總結(jié)

迪杰特斯拉算法

迪杰特斯拉算法是由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·迪杰特斯拉（Edsger W. Dijkstra）在1956年提出的，用于解決單源最短路徑問(wèn)題的經(jīng)典算法。該算法的目標(biāo)是從一個(gè)起始頂點(diǎn)找到到圖中其他頂點(diǎn)的最短路徑。

主要特點(diǎn)

適用于帶權(quán)圖，其中權(quán)重為非負(fù)數(shù)。（為什么只適用于非負(fù)數(shù)，因?yàn)榈辖芩固乩乃枷胧秦澬臏y(cè)量，當(dāng)有負(fù)權(quán)引入的時(shí)候，貪心策略將不再適用）解決從單個(gè)源點(diǎn)到其他所有頂點(diǎn)的最短路徑問(wèn)題。時(shí)間復(fù)雜度：當(dāng)使用優(yōu)先隊(duì)列（例如堆）時(shí)，復(fù)雜度為

O

(

E

log

?

V

)

O(E \log V)

O(ElogV)，其中

V

V

V 為頂點(diǎn)數(shù)量，

E

E

E 為邊的數(shù)量。

基本思想

Dijkstra算法通過(guò)不斷探索距離最近的頂點(diǎn)，逐步擴(kuò)展其最短路徑的已知范圍，直到找到從源點(diǎn)到所有其他頂點(diǎn)的最短路徑。該算法基于貪心策略：每一步選擇尚未處理的、距離源點(diǎn)最近的頂點(diǎn)進(jìn)行擴(kuò)展。

算法步驟

初始化：

將起始頂點(diǎn)的距離設(shè)為0，其余所有頂點(diǎn)的距離設(shè)為∞（表示不可達(dá)）。使用一個(gè)優(yōu)先隊(duì)列（或最小堆）來(lái)存儲(chǔ)頂點(diǎn)及其當(dāng)前的最短距離。 取距離源點(diǎn)最近的頂點(diǎn)，并標(biāo)記為已處理。 對(duì)于該頂點(diǎn)的每個(gè)鄰接頂點(diǎn)，更新其最短距離（如果通過(guò)當(dāng)前頂點(diǎn)可以獲得更短的路徑，則更新距離）。 重復(fù)步驟2和3，直到所有頂點(diǎn)都被處理過(guò)，或優(yōu)先隊(duì)列為空。

示例

實(shí)現(xiàn)迪杰斯特拉算法

基本步驟

首先假設(shè)我們有如下的一個(gè)圖： 灰色的點(diǎn)代表起點(diǎn)，我們需要從起點(diǎn)開始算每個(gè)點(diǎn)到起點(diǎn)的最短路徑。 第一步按照迪杰斯特拉的表述應(yīng)該將起點(diǎn)到起點(diǎn)的最短路徑初始化為0，起點(diǎn)到另外其他點(diǎn)的距離初始化為正無(wú)窮。 這里我們更新完s點(diǎn)之后，應(yīng)該更新和s點(diǎn)相連的點(diǎn)的最短路徑了，由于之前s到t點(diǎn)和到y(tǒng)點(diǎn)的最短路徑是正無(wú)窮，由于st和sy都小于兩個(gè)最短路徑，所以更新兩個(gè)最短路徑。 根據(jù)貪心策略，更新出來(lái)的兩個(gè)最短路徑，sy更小，所以我們應(yīng)該更新y相連的路徑。 所以接下來(lái)我們應(yīng)該更新y連接的點(diǎn)的最短路徑。 由于原本s到t的最短路徑是10，但是現(xiàn)在的最短路徑更新了之后是8，所以更新結(jié)果，由于之前s到x的最短路徑是正無(wú)窮，所以現(xiàn)在將最短路徑更新為14，s到z 也是相同的，因?yàn)橹暗淖疃搪窂绞钦裏o(wú)窮，所以現(xiàn)在將最短路徑更新為7. 在這三條最短路徑中選擇最短的那條： 這里就應(yīng)該以z為新的起點(diǎn) 更新z連接的頂點(diǎn)，z一共有兩條邊，一條是zs，一條是zx，由于s到s是最近的0，所以這里不需要更新，由于之前s到x的距離是14，所以這里更新s到x的距離。 接下來(lái)再?gòu)氖Ｏ碌倪呏校x擇最小的路徑。 從t點(diǎn)開始只有一條路徑，所以這里t到x，tx是1，由于之前的st的最短路徑是8，所以此時(shí)的最短路徑是9,9<13所以這里應(yīng)該更新最短路徑為9 這里最短路徑算是更新完了。

算法思路

由于這里我們涉及到最短路徑，所以應(yīng)該開辟一個(gè)dist數(shù)組，我們來(lái)想一想一個(gè)dist數(shù)組是否能解決問(wèn)題，很顯然是不能的，我們還需要一個(gè)數(shù)組，記錄當(dāng)前最短路徑的前一個(gè)頂點(diǎn)的下標(biāo)，在遍歷的時(shí)候我們可以索引每一個(gè)頂點(diǎn)了。 代碼展示：

void Dijkstra(const V& src, vector& dist, vector& pPath)

{

//獲取起點(diǎn)的下標(biāo)

size_t srci = GetVertexIndex(src);

//確定節(jié)點(diǎn)的數(shù)量

size_t n = _vertexs.size();

dist.resize(n, MAX_W);

pPath.resize(n, MAX_W);

//自己到自己的距離是0

dist[srci] = 0;

//自己的前一個(gè)是自己

pPath[srci] = srci;

//已經(jīng)確定最短路徑的頂點(diǎn)的集合

vector S(n, false);

for(size_t j=0;j

{

//選擇最短路徑頂點(diǎn)且不在s中更新其他路徑

int u = 0; //最小的那個(gè)點(diǎn)

W min = MAX_W; //最小權(quán)值

for (size_t i = 0;i < n;i++)

{

if (S[i] == false && dist[i] < min)

{

//選出最小的點(diǎn)

u = i;

//更新最小權(quán)值

min = dist[i];

}

}

//u被選出來(lái)

S[u] = true;

//松弛更新u連接出去的頂點(diǎn)v srci->u u->v

for (size_t v = 0;v < n;v++)

{

//確定u連接出去的所有邊

if (S[v] == false && _matrix[u][v] != MAX_W && (dist[u] + _matrix[u][v]) < dist[v])

{

dist[v] = dist[u] + _matrix[u][v];

//將v的父親更新為u

pPath[v] = u;

}

}

}

}

打印路徑節(jié)點(diǎn)和最短路徑：

//打印最短路徑

void PrinrtShotPath(const V& src, vector& dist, vector& pPath)

{

//獲取起點(diǎn)的下標(biāo)

size_t srci = GetVertexIndex(src);

//確定節(jié)點(diǎn)的數(shù)量

size_t n = _vertexs.size();

for (size_t i = 0;i < n;i++)

{

if (i != srci)

{

// 先找出i頂點(diǎn)的路徑

vector path;

size_t parenti = i;

//先將自己存進(jìn)去(自己不是原點(diǎn)先push進(jìn)去）

while (parenti != srci)

{

path.push_back(parenti);

parenti = pPath[parenti];

}

path.push_back(srci);

//將路徑逆置

reverse(path.begin(), path.end());

//打印出路徑

for (auto e : path)

{

cout << _vertexs[e] << "->";

}

//打印最短路徑

cout << dist[i];

cout << endl;

}

}

}

因?yàn)楦鶕?jù)最后一個(gè)節(jié)點(diǎn)去推上一個(gè)節(jié)點(diǎn)，推完之后數(shù)組中的節(jié)點(diǎn)會(huì)是一個(gè)反著的路徑，所以在打印的時(shí)候，應(yīng)該先把數(shù)組逆置，逆置之后再進(jìn)行打印。

總結(jié)

在本文中，我們深入探討了迪杰斯特拉算法的原理與應(yīng)用。作為一種經(jīng)典的最短路徑算法，迪杰斯特拉算法通過(guò)優(yōu)先隊(duì)列有效地解決了從單一源點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑問(wèn)題。我們分析了其時(shí)間復(fù)雜度和空間復(fù)雜度，了解了在不同圖形結(jié)構(gòu)下的性能表現(xiàn)。

通過(guò)示例和實(shí)現(xiàn)，我們不僅掌握了算法的基本步驟，還體驗(yàn)了其在實(shí)際應(yīng)用中的重要性。無(wú)論是在交通導(dǎo)航、網(wǎng)絡(luò)路由還是各種優(yōu)化問(wèn)題中，迪杰斯特拉算法都發(fā)揮著不可或缺的作用。

希望本文能夠幫助你更好地理解迪杰斯特拉算法，并為你在圖論和算法領(lǐng)域的進(jìn)一步學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。如果你有任何疑問(wèn)或想法，歡迎在評(píng)論區(qū)與我交流！

柚子快報(bào)激活碼778899分享：c++ 【圖論】迪杰特斯拉算法

http://yzkb.51969.com/

好文推薦