最短路各种算法步骤、原理及模板(c++)—更新中
dijkstra
速览:在联通带权图中寻找顶点a到顶点z的最短路径的长度。边 ( i , j ) (i, j) (i,j)的权值 w ( i , j ) > 0 w(i,j)>0 w(i,j)>0,且顶点的标注为 L ( x ) L(x) L(x),结束时, L ( z ) L(z) L(z)是从 a a a到 z z z的最短路径的长度。
找视频学习基本步骤
伪代码
dijkstra(w,a,z,L){
L(a)=0
for all vertices x!=a
L(x)=inf
T=set of all vertices // 临时标注的顶点集合,从a到有最短路径的顶点集合
// 没找到
while(z属于T){
choose v属于T with minimum L(v)
T=T-{v}
for each x属于T adjacent to v
L(x)=min{L(x),L(v)+w(v,x)}
}
}
证明
邻接矩阵暴力搜索版
void dijkstra_AdjMatrix(){
for (int i = 0; i < maxn; i++){
dis[i] = 0x1f1f1f1f; // 初始化到i点的最短路
}
memset(vis, 0, sizeof vis);
dis[1] = 0; // 到起始点的距离,可以改为起始点下标
for (int i = 1; i<n; i++){
int x = 0; // 当前dis最小的点
for (int j = 1; j <= n; j++){
if(!vis[j] && (x==0 || dis[j]<dis[x])) // 在T集合中,且自起始点路长最短
x = j;
}
vis[x] = 1; // 该点被从T集合中剔除
for (int j = 1; j<=n; j++){
dis[j] = min(dis[j], dis[x] + AdjMatrix[x][j]);
// 松弛操作 L(x)=min{L(x),L(v)+w(v,x)}
}
}
}
优先队列+邻接表
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
const int maxn = 1e4 + 7;
const int tempp = (1 << 31) - 1; // 注意左移符号优先级低于+-号
const int INF = 2147483647;
int n = 0;
// n为点的数目,m为边的数目
// Dijkstra
// 单源最短路
// 邻接表
// 优先队列
// 边权非负
// O(mlog(m))
struct edge { // 边
int v, w;
};
struct node { // 加入优先队列的节点
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
// 重载运算符,用于实现优先队列参数
};
vector<edge> e[maxn]; // vector邻接表
int dis[maxn], vis[maxn];
// dis为出发点到i节点最短距离,vis为是否松弛了该节点
priority_queue<node, vector<node>, greater<node> > q;
void dijkstra(int n, int s) {
for (int i = 0; i < maxn; i++){
dis[i] = INF;
}
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}
signed main(){
int m;
int s;
cin >> n >> m >> s; // 节点数,边数,起始节点编号
int a, b, diss;
for (int i = 0; i < m; i++){
cin >> a >> b >> diss;
edge temp;
temp.v = b;
temp.w = diss;
e[a].push_back(temp);
}
dijkstra(n, s);
for (int i = 1; i <= n; i++){
cout << dis[i] << " ";
}
return 0;
}