Dijkstra迪杰斯特拉算法及C++实现
Dijkstra算法是典型的最短路径路由算法，用来计算一个节点到其他所有节点的最短路径。算法的基本思想和流程是：
1. 初始化出发点到其它各点的距离dist[]以及各点的前一个访问点pre[]；
2. for(i=2…n){
找出dist[]中未访问过点中的最小值，记录为best；
以dist[best]为基准更新dist[]；
更新pre[]；
}
从1出发，第一次找到最小点2，更新dist[]，然后找到最小点4，以此类推，以当前最小为最优（贪心算法），列出下表：
| 迭代次数 | s | best | dist[2] | dist[3] | dist[4] | dist[5] |
|---|---|---|---|---|---|---|
| 1(初始化) | {1} | - | 10 | max | 30 | 100 |
| 2 | {1,2} | 2 | 10 | 60 | 30 | 100 |
| 3 | {1,2,4} | 4 | 10 | 50 | 30 | 90 |
| 4 | {1,2,4,3} | 3 | 10 | 50 | 30 | 60 |
| 5 | {1,2,4,3,5} | 5 | 10 | 50 | 30 | 60 |
具体实现：
#include <iostream>
#include <vector>
const int maxdist = 114514;
using namespace std;
/*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/
void Dijkstra(int n, int v, vector<int> &dist, vector<int> &pre, vector<vector<int>> &d){
vector<bool> s(n+1);
for (int i = 1; i <= n;i++){
dist[i] = d[v][i];
if (dist[i] < maxdist)
pre[i] = v;
else
pre[i] = 0;
}
dist[v] = 0;
s[v] = true;
for (int i = 2; i <= n;i++){//总迭代次数
int best = v;
int temp = maxdist;
for (int j = 1; j <= n;j++){//找到最小的距离
if (!s[j]&&dist[j]<temp){
temp = dist[j];
best = j;
}
}
s[best] = true;
for (int j = 1; j <= n;j++){//更新dist和pre
if (!s[j] && d[best][j] != maxdist){
int newdist = dist[best] + d[best][j];
if (newdist<dist[j]){
dist[j] = newdist;
pre[j] = best;
}
}
}
}
}
void printpath(vector<int> pre, int init, int fina){
int temp=fina;
vector<int> t;
while (temp != init){
t.push_back(temp);
temp = pre[fina];
fina = temp;
}
cout << init << "->";
for (int i = t.size(); i >1;i--)cout << t[i-1] << "->";
cout << t[0];
t.clear();
}
int main(){
int n, l;
cout << "请输入结点数和线数：";
cin >> n >> l;
vector<vector<int>> d(n+1, vector<int>(n+1));
for (int i = 1; i <= n;i++){
for (int j = 1; j <= n; j++)
d[i][j] = maxdist;
}
int p, q, len;
for (int i = 1; i <= l; ++i){
cin >> p >> q >> len;
if (len < d[p][q]){ // 有重边
d[p][q] = len; // p指向q
d[q][p] = len; // q指向p，这样表示无向图
}
}
vector<int> dist(n+1),pre(n+1);
for (int i = 1; i <= n; ++i)dist[i] = maxdist;
Dijkstra(n, 1, dist, pre, d);
cout << "点1到点n的最短路径长度: " << dist[n] << endl;
cout << "点1到点n的路径为: ";
printpath(pre, 1, n);
return 0;
}
#include <iostream>#include <vector>constint maxdist = 9999; usingnamespacestd; /*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/void Dijkstra(int n, int v, vector<int> &dist, vector<int> &pre, vector<vector<int>> &d) { vector<bool> s(n+1); for (int i = 1; i <= n;i++) { dist[i] = d[v][i]; if (dist[i] < maxdist) pre[i] = v; else pre[i] = 0; } dist[v] = 0; s[v] = true; for (int i = 2; i <= n;i++)//总的迭代次数 { int best = v; int temp = maxdist; for (int j = 1; j <= n;j++)//找到最小的距离 { if (!s[j]&&dist[j]<temp) { temp = dist[j]; best = j; } } s[best] = true; for (int j = 1; j <= n;j++)//更新dist和pre { if (!s[j] && d[best][j] != maxdist) { int newdist = dist[best] + d[best][j]; if (newdist<dist[j]) { dist[j] = newdist; pre[j] = best; } } } } } void printpath(vector<int> pre, int init, int fina) { int temp=fina; vector<int> t; while (temp != init) { t.push_back(temp); temp = pre[fina]; fina = temp; } cout << init << "->"; for (int i = t.size(); i >1;i--) { cout << t[i-1] << "->"; } cout << t[0]; t.clear(); } int main() { int n, l; cout << "请输入结点数和线数："; cin >> n >> l; vector<vector<int>> d(n+1, vector<int>(n+1)); for (int i = 1; i <= n;i++) { for (int j = 1; j <= n; j++) d[i][j] = maxdist; } int p, q, len; for (int i = 1; i <= l; ++i) { cin >> p >> q >> len; if (len < d[p][q]) // 有重边 { d[p][q] = len; // p指向q d[q][p] = len; // q指向p，这样表示无向图 } } vector<int> dist(n+1),pre(n+1); for (int i = 1; i <= n; ++i) dist[i] = maxdist; Dijkstra(n, 1, dist, pre, d); cout << "点1到点n的最短路径长度: " << dist[n] << endl; cout << "点1到点n的路径为: "; printpath(pre, 1, n); return0; } 标签：pre,dist,cout,temp,int,迪杰,C++,Dijkstra,vector From： https://www.cnblogs.com/BadJui/p/17031499.html