本篇內(nèi)容介紹了“Dijkstra單源最短路徑算法是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

在延慶等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作專(zhuān)業(yè)公司,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計(jì),成都全網(wǎng)營(yíng)銷(xiāo),外貿(mào)網(wǎng)站制作,延慶網(wǎng)站建設(shè)費(fèi)用合理。

單源最短路徑問(wèn)題

給定 加權(quán)有向圖G=(V,E,W)，每條邊的權(quán)值w為 非負(fù)數(shù)，表示兩個(gè)頂點(diǎn)間的距離。
源點(diǎn)s∈V。
求：從s出發(fā)到其他各個(gè)頂點(diǎn)的最短路徑。
 

如上圖所示，以1為源點(diǎn)，計(jì)算到其余各個(gè)頂點(diǎn)的最短距離（我已用紅線標(biāo)出）。下面列出了最終解：

源點(diǎn)：1
1->6->2 : short[2] = 5
1->6->2->3 : short[3] = 12
1->6->4 : short[4] = 9
1->6->5 : short[5] = 4
1->6v : short[6] = 3

Dijkstra算法相關(guān)概念

S集合：當(dāng)從s到x（x ∈V ）的最短路徑找到時(shí)，則x ∈S。當(dāng)所有頂點(diǎn)都進(jìn)入S集合時(shí)，算法結(jié)束。

初始：S=｛s｝，當(dāng)S=V時(shí)算法結(jié)束。

從s到u相對(duì)于S的最短路徑：指從s到u且僅經(jīng)過(guò)S中頂點(diǎn)的最短路徑。

dist[u]:從s到u相對(duì)于S的最短路徑長(zhǎng)度

short[u]:從s到u最短路徑的長(zhǎng)度（算法最終解）

dist[u] ≥ short[u]

Dijkstra算法采用貪心算法模式，算法過(guò)程就是通過(guò)計(jì)算dist[u],不斷擴(kuò)充S集合，同時(shí)dist[u]會(huì)不斷優(yōu)化改善，直到dist[u] = short[u]，并將其放到S中，當(dāng)所有頂點(diǎn)都放入S集合時(shí)，算法結(jié)束。

算法設(shè)計(jì)思想

輸入：加權(quán)有向圖G=(V,E,W)
          V={1,2,…,n}, s=1

輸出：從s到每個(gè)頂點(diǎn)的最短路徑

1. 初始S=｛1｝

2. 對(duì)于u ∈V-S,計(jì)算1到u的相對(duì)于S的最短路，長(zhǎng)度為dist[u]

3. 選擇V-S中dist值最小的那個(gè)頂點(diǎn)，加入S。

4. 繼續(xù)上述過(guò)程，直到S=V為止。

實(shí)例

輸入：G=(V,E,W)，源點(diǎn)1

          V={1,2,3,4,5,6}
 

當(dāng)把6號(hào)頂點(diǎn)放進(jìn)S集合后，經(jīng)由6號(hào)頂點(diǎn)出發(fā)到達(dá)的頂點(diǎn)的最短距離可能會(huì)被優(yōu)化更新，因?yàn)樵撍惴ǖ乃枷牒堋柏澬摹?，誰(shuí)更短我要誰(shuí)！比如1->6->2要比1->2距離更短，所以dist[2]被更新為5，從專(zhuān)業(yè)術(shù)語(yǔ)上講，這個(gè)“更新”過(guò)程叫做松弛，其他點(diǎn)同理。然后從dist[u]里找出最短的路徑的那個(gè)頂點(diǎn)（5號(hào)），并放進(jìn)S集合里。

  S={1,6}
  dist[1] = 0
  dist[6] = 3
  dist[2] = 5
  dist[4] = 9
  dist[5] = 4
  dist[3] = ∞

  S={1,6,5,2}
  dist[1] = 0
  dist[6] = 3
  dist[5] = 4
  dist[2] = 5
  dist[4] = 9
  dist[3] = 12

  S={1,6,5,2,4,3}
  dist[1] = 0
  dist[6] = 3
  dist[5] = 4
  dist[2] = 5
  dist[4] = 9
  dist[3] = 12

當(dāng)有向圖中的所有頂點(diǎn)都進(jìn)入了S集合后，算法結(jié)束，此時(shí)的dist[u]的值其實(shí)就是最初我們找出的那個(gè)最終解short[u]，所以，算法結(jié)束時(shí)，dist[u]=short[u],得到最終解。

“Dijkstra單源最短路徑算法是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！