Dijkstra演算法總結
一、Dijkstra 演算法的定義
老規矩先參考一下百度百科上關于 Dijkstra 演算法的說明，
迪杰斯特拉演算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉演算法，是從一個頂點到其余各頂點的最短路徑演算法，解決的是有權圖中最短路徑問題，迪杰斯特拉演算法主要特點是從起始點開始，采用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止，
很顯然，根據這段文字，我們可以了解到 Dijkstra 演算法應用了貪心演算法的思想，主要應用于有權圖中最短路徑問題，
二 、Dijkstra 演算法的操作程序
因為這一演算法的思路是從起始點開始，采用貪心演算法的策略，每次遍歷到離起始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止，所以要實作這一想法，我們需要一個計算從起始點到各個頂點的最短路程的陣列 dis [] ，
假設起始點為 start ，那么初始狀態下，dis [ start ] = 0；
如果這個點的出度為零，將除起始點以外所有點的 dis [] 值賦為無窮大，這樣便于在之后的遍歷中如果找到路徑，就能通過比較選取兩者中較小的作為最短路程；
如果這個點的出度不為零，那么說明存在有向邊由這個點指向其他點，假設終點為 end ，有向邊為 （ start ，end ），邊權（邊的長度）為 w（ start ，end ），則 dis [ end ] = w（ start ，end ）；
重點！！！
若這個點的出度大于等于 2的時候，下次找離這個點最近的終點作為起始點，即尋找由這個點引出的邊權最小的有向邊來進行下一步操作，我們可以反推一下這樣做的原因，假設這個點出度為二，由這個點引出的邊權小的有向邊為 A ，大的為 B ，如果我們選擇了 B 的話，那么想要到 A ，最好的情況是只通過 B 這一個中轉點，由 B 到 A，因為所有邊的邊權均為整數，到 B 的路程原本就大于 A，再加上由 B 到 A 的路程，就更不用說了，所以可以判斷出從起始點直接到 A 一定是最短路徑，所以將 A 作為下一次的起始點一定是正確的，
然后按照同樣的思路重復上述操作，直到所有的點都被取完，
接下來我以下圖為例，模擬一下整個程序，
第一步：
一號可以通向二號和三號，所以把二號和三號賦上值，
第二步：
三號可以通向四號和五號，所以把四號和五號賦上值，
第三步：
因為 w（ 3 ，4 ）< w（ 3 ，5 ），所以選擇四號，四號通向五號，1-3-4-5 這條路徑上的權值之和為 7 ，7 < 8 ，所以用 7 來替換 8 ，
總結一下，
這就是最基本的 Dijkstra 演算法的實作，
三、Dijkstra 演算法例題應用
下面以單源最短路為例實際應用 Dijkstra 演算法，
題目描述
給出一個有向圖，請輸出從某一點出發到所有點的最短路徑長度，
輸入格式
第一行包含三個整數 n,m,s，n,m,s，分別表示點的個數、有向邊的個數、出發點的編號，接下來 m 行每行包含三個整數 u,v,w，u,v,w，表示一條 u→v 的，長度為 w 的邊，
輸出格式
輸出一行 n 個整數，第 i 個表示 s 到第 i 個點的最短路徑，若不能到達則輸出 2^31-1，
輸入輸出樣例
輸入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
輸出
0 2 4 3
#include<bits/stdc++.h>
using namespace std;
long long head[100005],to[200005],nxt[200005],len[200005],cnt,a[100005];
bool b[100005];
void cwy(int x,int y,int z){
cnt++;
to[cnt]=y;
len[cnt]=z;
nxt[cnt]=head[x];
head[x]=cnt;
}//鏈式前向星；
priority_queue< pair<int,int> > q;//使用優先佇列來維護 Dijkstra 演算法；
int main(){
int n,m,x,y,z,s;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
cwy(x,y,z);
}
for(int i=1;i<=n;i++){
a[i]=0x7f;//正無窮大的賦值；
}
a[s]=0;//起始點本身賦零；
q.push(make_pair(0,s));
while(q.empty()==0){
int x=q.top().second;
q.pop();
if(b[x]){
continue;
}
b[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i],l=len[i];
if(a[y]>a[x]+l){
a[y]=a[x]+l;
q.push(make_pair(-a[y],y));
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
return 0;
}
謝謝閱讀！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256376.html
標籤：其他
上一篇：位元組、位與二進制表示
下一篇：C語言中資料的存盤