迪杰斯特拉算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法薪捍。是從一個頂點到其余各頂點的最短路徑算法，解決的是有權圖中最短路徑問題陵刹。迪杰斯特拉算法主要特點是從起始點開始啃洋，采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節(jié)點惫东，直到擴展到終點為止莉给。
樸素Dijkstra適用于求稠密圖,時間復雜度n * n,用鄰接矩陣求存儲。
思想：看的我們數(shù)據(jù)結構老師的ppt看懂的
在這里插入圖片描述
在這里插入圖片描述
例如從起點1到其他點的最短距離
在這里插入圖片描述
代碼模板
int Dijkstra(){
memset(dist,0x3f,sizeof dist); //初始化距離 注意這行是把dist[i]初始化為0x3f3f3f3f了而不是0x3f3f
dist[1] = 0; //如果要是求第i個點到其他點的距離廉沮，就dist[i] = 0;
for(int i = 1; i <= n; i++){ //n次迭代颓遏，每次求出離起點最短的距離，并把該點加到s集合中滞时，然后更新其他點
int t = -1;
for(int j = 1; j<=n; j++)
if(!st[j] && (dist[j] < dist[t] || t == -1)) //找到不在集合中且距離最近的點
t = j;
for(int j = 1;j <= n;j++)
dist[j] = min(dist[j],dist[t] + g[t][j]); //更新其他點
st[t] = true;
}
if(dist[n] == 0x3f3f3f3f)
return -1;
return dist[n];
}
沒有注釋的代碼
int Dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1;i <= n;i++){
int t = -1;
for(int j = 1;j <= n;j++)
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
for(int j = 1;j<=n;j++)
dist[j] = min(dist[j],dist[t] + g[t][j]);
st[t] = true;
}
if(dist[n] == 0x3f3f3f3f)
return -1;
return dist[n];
}
例題
給定一個n個點m條邊的有向圖叁幢，圖中可能存在重邊和自環(huán)，所有邊權均為正值坪稽。
請你求出1號點到n號點的最短距離曼玩，如果無法從1號點走到n號點，則輸出-1窒百。
輸入格式
第一行包含整數(shù)n和m黍判。
接下來m行每行包含三個整數(shù)x，y篙梢，z顷帖，表示存在一條從點x到點y的有向邊，邊長為z渤滞。
輸出格式
輸出一個整數(shù)贬墩，表示1號點到n號點的最短距離。
如果路徑不存在蔼水，則輸出-1震糖。
數(shù)據(jù)范圍
1≤n≤50,
1≤m≤10^5,
圖中涉及邊長均不超過10000。
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3
代碼
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N];
int dist[N];
bool st[N];
int n, m;
int x ,y ,z;
int Dijkstra();
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g); //題目說存在重邊趴腋，所以我們要存最小的那條邊,這里初始化為無窮大
while(m--){
cin>>x>>y>>z;
g[x][y] = min(z,g[x][y]);
}
cout<<Dijkstra()<<endl;
return 0;
}
int Dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1;i <= n;i++){
int t = -1;
for(int j = 1;j <= n;j++)
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
for(int j = 1;j<=n;j++)
dist[j] = min(dist[j],dist[t] + g[t][j]);
st[t] = true;
}
if(dist[n] == 0x3f3f3f3f)
return -1;
return dist[n];
}
