正文

經(jīng)過所有點的最短路徑算法（經(jīng)過所有的點求最短的路線）

發(fā)布時間：2023-04-22 06:09:32 稿源：創(chuàng)意嶺閱讀： 124

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關(guān)于經(jīng)過所有點的最短路徑算法的問題，以下是小編對此問題的歸納整理，讓我們一起來看看吧。

開始之前先推薦一個非常厲害的Ai人工智能工具，一鍵生成原創(chuàng)文章、方案、文案、工作計劃、工作報告、論文、代碼、作文、做題和對話答疑等等

只需要輸入關(guān)鍵詞，就能返回你想要的內(nèi)容，越精準(zhǔn)，寫出的就越詳細(xì)，有微信小程序端、在線網(wǎng)頁版、PC客戶端

官網(wǎng)：https://ai.de1919.com。

創(chuàng)意嶺作為行業(yè)內(nèi)優(yōu)秀的企業(yè)，服務(wù)客戶遍布全球各地，如需了解SEO相關(guān)業(yè)務(wù)請撥打電話175-8598-2043，或添加微信：1454722008

本文目錄:

1、數(shù)據(jù)結(jié)構(gòu)之圖：求所有節(jié)點之間的最短路徑，用什么算法時間復(fù)雜度??？求答案與解釋
2、最短路徑 | 深入淺出Dijkstra算法（一）
3、圖遍歷算法之最短路徑Dijkstra算法
4、最短路Dijkstra算法怎么求起點到終點經(jīng)過的路程，就是把經(jīng)過的每個點都顯示出來，用c和c++都可，大牛來吧

經(jīng)過所有點的最短路徑算法（經(jīng)過所有的點求最短的路線）

一、數(shù)據(jù)結(jié)構(gòu)之圖：求所有節(jié)點之間的最短路徑，用什么算法時間復(fù)雜度??？求答案與解釋

兩者時間復(fù)雜度一般都是O(n3)，但對于稀疏圖來說重復(fù)使用Dijkstra方法比較好！

Dijkstra算法時間復(fù)雜度為O（V*V+E）,可以用優(yōu)先隊列進(jìn)行優(yōu)化，優(yōu)化后時間復(fù)雜

度變?yōu)?（v*lgn）。

源點可達(dá)的話，O（V*lgV+E*lgV）=>O（E*lgV）。

當(dāng)是稀疏圖的情況時，此時E=V*V/lgV，所以算法的時間復(fù)雜度可為O（V^2） ?？梢杂脙?yōu)先隊列進(jìn)行優(yōu)化，優(yōu)化后時間復(fù)雜度變?yōu)?（v*lgn）。

具體詳細(xì)解釋你可以看看這個http://blog.chinaunix.net/uid-27164517-id-3287891.html。

二、最短路徑 | 深入淺出Dijkstra算法（一）

上次我們介紹了神奇的只有 五行的 Floyd-Warshall 最短路算法 ，它可以方便的求得 任意兩點的最短路徑， 這稱為 “多源最短路”。

這次來介紹 指定一個點（源點）到其余各個頂點的最短路徑， 也叫做 “單源最短路徑”。 例如求下圖中的 1 號頂點到 2、3、4、5、6 號頂點的最短路徑。

與 Floyd-Warshall 算法一樣，這里仍然 使用二維數(shù)組 e 來存儲頂點之間邊的關(guān)系， 初始值如下。

我們還需要用 一個一維數(shù)組 dis 來存儲 1 號頂點到其余各個頂點的初始路程， 我們可以稱 dis 數(shù)組為 “距離表”， 如下。

我們將此時 dis 數(shù)組中的值稱為 最短路的“估計值”。

既然是 求 1 號頂點到其余各個頂點的最短路程， 那就 先找一個離 1 號頂點最近的頂點。

通過數(shù)組 dis 可知當(dāng)前離 1 號頂點最近是 2 號頂點。 當(dāng)選擇了 2 號頂點后，dis[2]的值就已經(jīng)從“估計值”變?yōu)榱恕按_定值”， 即 1 號頂點到 2 號頂點的最短路程就是當(dāng)前 dis[2]值。

為什么呢？你想啊，目前離 1 號頂點最近的是 2 號頂點，并且這個圖所有的邊都是正數(shù)，那么肯定不可能通過第三個頂點中轉(zhuǎn)，使得 1 號頂點到 2 號頂點的路程進(jìn)一步縮短了。因此 1 號頂點到其它頂點的路程肯定沒有 1 號到 2 號頂點短，對吧 O(∩_∩)O~

既然選了 2 號頂點，接下來再來看 2 號頂點 有哪些出邊呢。有 2->3 和 2->4 這兩條邊。

先討論 通過 2->3 這條邊能否讓 1 號頂點到 3 號頂點的路程變短。 也就是說現(xiàn)在來比較 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 號頂點到 3 號頂點的路程，dis[2]+e[2][3]中 dis[2]表示 1 號頂點到 2 號頂點的路程，e[2][3]表示 2->3 這條邊。所以 dis[2]+e[2][3]就表示從 1 號頂點先到 2 號頂點，再通過 2->3 這條邊，到達(dá) 3 號頂點的路程。

我們發(fā)現(xiàn) dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新為 10。這個過程有個專業(yè)術(shù)語叫做 “松弛” 。即 1 號頂點到 3 號頂點的路程即 dis[3]，通過 2->3 這條邊 松弛成功。 這便是 Dijkstra 算法的主要思想：通過 “邊” 來松弛 1 號頂點到其余各個頂點的路程。

同理通過 2->4（e[2][4]），可以將 dis[4]的值從 ∞ 松弛為 4（dis[4]初始為 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新為 4）。

剛才我們對 2 號頂點所有的出邊進(jìn)行了松弛。松弛完畢之后 dis 數(shù)組為：

接下來，繼續(xù)在剩下的 3、4、5 和 6 號頂點中，選出離 1 號頂點最近的頂點。通過上面更新過 dis 數(shù)組，當(dāng)前離 1 號頂點最近是 4 號頂點。此時，dis[4]的值已經(jīng)從“估計值”變?yōu)榱恕按_定值”。下面繼續(xù)對 4 號頂點的所有出邊（4->3，4->5 和 4->6）用剛才的方法進(jìn)行松弛。松弛完畢之后 dis 數(shù)組為：

繼續(xù)在剩下的 3、5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 3 號頂點。此時，dis[3]的值已經(jīng)從“估計值”變?yōu)榱恕按_定值”。對 3 號頂點的所有出邊（3->5）進(jìn)行松弛。松弛完畢之后 dis 數(shù)組為：

繼續(xù)在剩下的 5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 5 號頂點。此時，dis[5]的值已經(jīng)從“估計值”變?yōu)榱恕按_定值”。對5號頂點的所有出邊（5->4）進(jìn)行松弛。松弛完畢之后 dis 數(shù)組為：

最后對 6 號頂點的所有出邊進(jìn)行松弛。因為這個例子中 6 號頂點沒有出邊，因此不用處理。 到此，dis 數(shù)組中所有的值都已經(jīng)從“估計值”變?yōu)榱恕按_定值”。

最終 dis 數(shù)組如下，這便是 1 號頂點到其余各個頂點的最短路徑。

OK，現(xiàn)在來總結(jié)一下剛才的算法。 Dijkstra算法的基本思想是：每次找到離源點（上面例子的源點就是 1 號頂點）最近的一個頂點，然后以該頂點為中心進(jìn)行擴(kuò)展，最終得到源點到其余所有點的最短路徑。

基本步驟如下：

在博客中看到兩個比較有趣的問題，也是在學(xué)習(xí)Dijkstra時，可能會有疑問的問題。

當(dāng)我們看到上面這個圖的時候，憑借多年對平面幾何的學(xué)習(xí)，會發(fā)現(xiàn)在“三角形ABC”中，滿足不了 構(gòu)成三角形的條件(任意兩邊之和大于第三邊)。 納尼，那為什么圖中能那樣子畫？

還是“三角形ABC”，以A為起點，B為終點，如果按照平面幾何的知識， “兩點之間線段最短”， 那么，A到B的最短距離就應(yīng)該是6(線段AB)，但是，實際上A到B的最短距離卻是3+2=5。這又怎么解釋？

其實，之所以會有上面的疑問，是因為 對邊的權(quán)值和邊的長度這兩個概念的混淆， 。之所以這樣畫，也只是為了方便理解（每個人寫草稿的方式不同，你完全可以用別的方式表示，只要便于你理解即可）。

PS：數(shù)組實現(xiàn)鄰接表可能較難理解，可以看一下這里

參考資料：

Dijkstra算法是一種基于貪心策略的算法。每次新擴(kuò)展一個路程最短的點，更新與其相鄰的點的路程。當(dāng)所有邊權(quán)都為正時，由于不會存在一個路程更短的沒擴(kuò)展過的點，所以這個點的路程永遠(yuǎn)不會再被改變，因而保證了算法的正確性。

根據(jù)這個原理， 用Dijkstra算法求最短路徑的圖不能有負(fù)權(quán)邊， 因為擴(kuò)展到負(fù)權(quán)邊的時候會產(chǎn)生更短的路徑，有可能破壞了已經(jīng)更新的點路徑不會發(fā)生改變的性質(zhì)。

那么，有沒有可以求帶負(fù)權(quán)邊的指定頂點到其余各個頂點的最短路徑算法（即“單源最短路徑”問題）呢？答案是有的， Bellman-Ford算法 就是一種。（我們已經(jīng)知道了 Floyd-Warshall 可以解決“多源最短路”問題，也要求圖的邊權(quán)均為正）

通過 鄰接矩陣 的Dijkstra時間復(fù)雜度是。其中每次找到離 1 號頂點最近的頂點的時間復(fù)雜度是 O(N)，這里我們可以用 優(yōu)先隊列（堆） 來優(yōu)化，使得這一部分的時間復(fù)雜度降低到。這個我們將在后面討論。

三、圖遍歷算法之最短路徑Dijkstra算法

最短路徑問題是圖論研究中一個經(jīng)典算法問題，旨在尋找圖中兩節(jié)點或單個節(jié)點到其他節(jié)點之間的最短路徑。根據(jù)問題的不同，算法的具體形式包括：

常用的最短路徑算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改進(jìn)版本），F(xiàn)loyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文將重點介紹Dijkstra算法的原理以及實現(xiàn)。

Dijkstra算法，翻譯作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷蘭計算機科學(xué)家艾茲赫爾.戴克斯特拉提出，用于解決賦權(quán)有向圖的 單源最短路徑問題 。所謂單源最短路徑問題是指確定起點，尋找該節(jié)點到圖中任意節(jié)點的最短路徑，算法可用于尋找兩個城市中的最短路徑或是解決著名的旅行商問題。

問題描述 ：在無向圖中，為圖節(jié)點的集合，為節(jié)點之間連線邊的集合。假設(shè)每條邊的權(quán)重為，找到由頂點到其余各個節(jié)點的最短路徑（單源最短路徑）。

為帶權(quán)無向圖，圖中頂點分為兩組，第一組為已求出最短路徑的頂點集合（用表示）。初始時只有源點，當(dāng)求得一條最短路徑時，便將新增頂點添加進(jìn) ，直到所有頂點加入中，算法結(jié)束。第二組為未確定最短路徑頂點集合（用表示），隨著中頂點增加，中頂點逐漸減少。

以下圖為例，對Dijkstra算法的工作流程進(jìn)行演示（以頂點為起點）：

注：

01）是已計算出最短路徑的頂點集合；

02）是未計算出最短路徑的頂點集合；

03）表示頂點到頂點的最短距離為3

第1步 ：選取頂點添加進(jìn)

第2步 ：選取頂點添加進(jìn) ，更新中頂點最短距離

第3步 ：選取頂點添加進(jìn) ，更新中頂點最短距離

第4步 ：選取頂點添加進(jìn) ，更新中頂點最短距離

第5步 ：選取頂點添加進(jìn) ，更新中頂點最短距離