无向图有向图都可用 无向图只是有向图的一种
只需枚举到 $n-1$个点即可 最后一个点$n$没有出度 无需枚举
单源最短路 ：
从你指定的点 走到所有路径的点最短
为什么从0号点开始初始化无穷大
0号点作为哨兵 来控制$u$的赋值 来找到最小值. 自己手动模拟一下即可
d[i]数组 存i号点走到指定的点的最小值
vis[i] 看是否被访问过，防止成环
算法流程
初始时 所有点初始化为正无穷大 ， 指定的点 距离为$0$ , $d[x] = 0$
枚举每一个点 ，在枚举的过程中 不断往外拓展,不过在拓展之前
先检查当前层的最短路径 , 而$u$ 一开始是从0开始距离无穷大 也就是相当于一个哨兵
不断更新选取最小距离
1
2
3
|
int u = 0;
for(int j = 1;j<=n;++j)
if(!vis[j] && d[j] < d[u]) u = j;//往下一個點走
|
确定完最小距离的点 再往外层层拓展 更新路径的最小距离
1
2
3
4
5
6
|
for(int j = h[u]; ~j;j = e[j].next){
//松弛
int v = e[j].v;
int w = e[j].w;
if(d[u] + w < d[v]) d[v] = d[u] + w;
}
|
按照贪心的想法想就会简单很多
复杂度 最坏为$o(n^2 + m)$
若对于稠密图 $n = 10 ^3$ $ m = 10 ^ 6$ $10^{3+3} + 10^{6}$ 是可以AC的
对于稀疏图 $n = 10^6 , m = 10 ^ 6$ 级别 就TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int d[N];
bool vis[N];
void dj(int x){
for(int i = 0;i<=n;++i) d[i] = inf;//0?
d[x] = 0;
for(int i = 1;i<n;++i){
int u = 0;
for(int j = 1;j<=n;++j)
if(!vis[j] && d[j] < d[u]) u = j;//往下一個點走
vis[u] = true;
for(int j = h[u]; ~j;j = e[j].next){
//松弛
int v = e[j].v;
int w = e[j].w;
if(d[u] + w < d[v]) d[v] = d[u] + w;
}
}
}
|
瓶颈就在找最小点
显然可以用堆来维护最小距离的点 pair默认按照第一个排序 可以用小根堆
但是泛型要写很长，所以加个负号q.push({-d[v],v});
每个点的最短路可能会被更新多次
第一遍存完全部边 然后进行调整 第二遍都不会进行调整 因为找不到最小值了 就退出循环。每次调整是$logm$级别 总的复杂度$o(mlogm)$
用队列会有垄余元素， 最多存有m个边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int d[N];
bool vis[N];
void dj2(int x){
for(int i = 0;i<=n;++i) d[i] = inf;
q.push({0,x});d[x] = 0;
while(q.size()){
auto p = q.top();q.pop();
int u = p.second;
//这个点之前已经更新过
if(vis[u]) continue;
vis[u] = true;
for(int j = h[u]; ~j;j = e[j].next){
//松弛
int v = e[j].v;
int w = e[j].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
q.push({-d[v],v});
}
}
}
}
//如果d[n] == inf ， 说明走不到n 或 不存在最短路
|
有缺陷 无法处理负边权值 , 为什么呢
比如A点的出度 有B,C两点 这时候要枚举最小的路径然后更新 假设此时走B是走C小的。但是 如果C后面有一条路的权值是负非常大的数 甚至都超过 走B的路径总和. 而你又选了B路 显然是不对的。
dj算法确认了每个点后 该点就被vis数组标记了 你不能往回走 而如果有负权 那个确定的点就不一定是最短路了 后面可能会出现负值
如上 你在当前选择了最小的B路径 那也只是当前最小
路径存储
每次找到最小值 则保存路径即可 开个路径数组 然后dfs 深搜打印
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
const int N = 114514;
int d[N];
bool vis[N];
int path[N];
void dj3(int x){
for(int i = 0;i<=n;++i) d[i] = inf;
q.push({0,x});d[x] = 0;
while(q.size()){
auto p = q.top();q.pop();
int u = p.second;
if(vis[u]) continue;
vis[u] = true;
for(int j = h[u]; ~j;j = e[j].next){
//松弛
int v = e[j].v;
int w = e[j].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
q.push({-d[v],v});
//找到最小路径 保存下
path[v] = u;//出度v是从最小的入度u来的
}
}
}
}
|
作业 试试写出dfs打印路径的方式
1
|
void dfs(int u,int x){}//其中u为起点,x为终点
|
答案:
1
2
3
4
5
6
7
8
|
void dfs(int u,int x){
if(u == x){
printf("%d\n",u);
return;
}
dfs(pre[u],x);
printf("%d\n",u);
}
|
总结：
没优化的dj不适合稠密图 ,都不能判负权值，负环
bfs
最小步数 边权为1的dijkstra
适用于规模$10^{7}$
作业
P3371 【模板】单源最短路径（弱化版）：Dijkstra、SPFA
P4779 【模板】单源最短路径（标准版）：Dijkstra