最短路算法——Dijkstra
Dijkstra
Ⅰ 单源最短路问题
在带权图 G = (V, E) 中,每条边都有一个权值 ,即边的长度。路径的长度为路径上所有边权之和。单源最短路问题是指:求源点到图中其余各顶点的最短路径。
解决单源最短路径问题常用 Dijkstra 算法,用于计算一个顶点到其他所有顶点的最短路径。Dijkstra 算法的主要特点是以起点为中心,逐层向外扩展(这一点类似于 bfs,但是不同的是,bfs 每次扩展一个层,但是 Dijkstra 每次只会扩展一个点),每次都会取一个最近点继续扩展,直到取完所有点为止。
注意:Dijkstra 算法要求图中不能出现负权边。
Ⅱ 算法流程
我们定义带权图 G 所有顶点的集合为 V,接着我们再定义已确定从源点出发的最短路径的顶点集合为 U,初始集合 U 为空,记从源点 s 出发到每个顶点 v 的距离为 distv,初始 dists = 0。接着执行以下操作:
1. 从 V − U 中找出一个距离源点最近的顶点 v,将 v 加入集合 U 。
2. 并用 distv 和顶点 v 连出的边来更新和 v 相邻的、不在集合 U 中的顶点的 dist,这一步称为松弛操作。
3. 重复步骤 1 和 2,直到 V = U 或找不出一个从 s 出发有路径到达的顶点,算法结束。如果最后 V ≠ U,说明有顶点无法从源点到达;否则每个 disti 表示从 s 出发到顶点 i的最短距离。Dijkstra 算法的时间复杂度为 O(V ²),其中 V 表示顶点的数量。
Ⅲ 算法演示
此时 U = V,算法结束,单源最短路计算完毕。
Ⅳ 参考代码
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
struct edge {
int v, w, next;
edge() {
}
edge(int _v, int _w, int _next) {
v = _v;
w = _w;
next = _next;
}
} e[M << 1];
int head[N], len;
void init() {
len = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) {
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w) {
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijstra(int u) {
memset(vis, false, sizeof(vis));
memset(dis, INF, sizeof(dis));//全部赋值为极大值
dis[u] = 0;//第一个点赋值为0
for(int i = 0; i < n; i++) {
int mi = INF;
for(int j = 1; j <= n; j++) {
if(!vis[j] && dis[j] < mi) {
mi = dis[u = j];
}
}
if(mi == INF) {
return ;
}
vis[u] = true;
for(int j = head[u]; ~j; j = e[j].next){
int v = e[j].v;
int w = e[j].w;
if(!vis[v] && dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
}
}
}
}
int main() {
init();//初始化
int u, v, w;
cin >> n >> m;
while(m--) {
cin >> u >> v >> w;
add2(u, v, w);
}
dijstra(1);//计算最短路
cout << dis[n] << endl;//输出
return 0;
}