1、Dijkstra算法介紹

·

算法起源：

·

Djkstra 算法是一種用于計算帶權有向圖中單源最短路徑(SSSP:Single-Source Shortest Path)的算法，由計算機科學家Edsger Djkstra于1956年構思并于1959年發表。其解決的問題是:給定圖和源頂點v，找到從v至圖中所有頂點的最短路徑。

·

算法特點：

·

Dijkstra算法使用了廣度優先搜索解決賦權有向圖或者無向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。

·

基本思想

·

1.通過Dijkstra計算圖G中的最短路徑時，需要指定起點s(即從頂點s開始計算)。

2.此外，引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(以及相應的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)。

3.初始時，S中只有起點s；U中是除s之外的頂點，并且U中頂點的路徑是”起點s到該頂點的路徑”。然后，從U中找出路徑最短的頂點，并將其加入到S中；接著，更新U中的頂點和頂點對應的路徑。然后，再從U中找出路徑最短的頂點，并將其加入到S中；接著，更新U中的頂點和頂點對應的路徑。… 重復該操作，直到遍歷完所有頂點。

·

操作步驟

·

1.初始時，S只包含起點s；U包含除s外的其他頂點，且U中頂點的距離為”起點s到該頂點的距離”[例如，U中頂點v的距離為(s,v)的長度，然后s和v不相鄰，則v的距離為∞]。

2.從U中選出”距離最短的頂點k”，并將頂點k加入到S中；同時，從U中移除頂點k。

3.更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k來更新其它頂點的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。

4.重復步驟(2)和(3)，直到遍歷完所有頂點。

單純的看上面的理論可能比較難以理解，下面通過實例來對該算法進行說明。

圖解2.

以下B節點中23應為13。

初始狀態：S是已計算出最短路徑的頂點集合，U是未計算除最短路徑的頂點的集合！

圖解2.

求從頂點v1到其他各個頂點的最短路徑

這個圖解相對簡單，易于理解

我們最后得到的結果為：

起點 終點 最短路徑 長度v1 v2 無 ∞v3 {v1,v3} 10v4 {v1,v5,v4} 50v5 {v1,v5} 30v6?????{v1，v5,v4,v6}?60

附加一道例題供大家練習：

洛谷 P3371 【模板】單源最短路徑

參考代碼如下：

#includeusing namespace std;#define maxn 10005#define maxm 500005#define INF 1234567890inline int read(){int x=0,k=1; char c=getchar();while(c'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;}struct Edge{int u,v,w,next;}e[maxm];int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn];struct node{int w,now;inline bool operator x.w;//這里注意符號要為'>'}};priority_queueq;//優先隊列，其實這里一般使用一個pair，但為了方便理解所以用的結構體inline void add(int u,int v,int w){e[++cnt].u=u;//這句話對于此題不需要，但在縮點之類的問題還是有用的e[cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];//存儲該點的下一條邊head[u]=cnt;//更新目前該點的最后一條邊(就是這一條邊)}//鏈式前向星加邊void dijkstra(){for(int i=1;i<=n;i++){dis[i]=INF;}dis[s]=0;//賦初值q.push((node){0,s});while(!q.empty())//堆為空即為所有點都更新{node x=q.top();q.pop();int u=x.now;//記錄堆頂(堆內最小的邊)并將其彈出if(vis[u]) continue;//沒有遍歷過才需要遍歷vis[u]=1;for(int i=head[u];i;i=e[i].next)//搜索堆頂所有連邊{int v=e[i].v;if(dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;//松弛操作q.push((node){dis[v],v});//把新遍歷到的點加入堆中}}}}int main(){n=read(),m=read(),s=read();for(int i=1,x,y,z;i<=m;i++){x=read(),y=read(),z=read();add(x,y,z);}dijkstra();for(int i=1;i<=n;i++){printf("%d ",dis[i]);}return 0;}

文中很多干貨，寫這篇文章目的就是希望這篇文章可以幫到有需要的人。希望喜歡的同學可以多多轉發到朋友圈、點擊文章右下角“在看”，這就是對我們最大的鼓勵啦，謝謝支持。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的最短路dijkstra算法详解_最短路径问题---Dijkstra算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。