单源最短路
- 就是从一个起点到终点的问题
边权为正数:
朴素Dijkstra算法(贪心)
- 时间复杂度是
- 但是时间复杂度与边数无关，与问题规模有关，适用于解决 稠密图
- 首先有起点，每次找到一个距离起点最近的点，找到之后记录找过，再用这个点到其他点的距离来更新起点到其他点的距离，再找一个次近的点（没记录过），再更新，一直找到最后一个点（n）
- 找n个点，每个点更新之后点的距离，两个循环
- 稠密图要用邻接矩阵来存
具体实现
- 开一个邻接矩阵，存下边数和权重，可全初始化为无穷（0x3f3f3f3f）
- 开一个数组存起点到各个点的距离
- 每次查找 没有找过的， 距离起点最近的点，用其权重（到其他点的距离）来更新起点到每个点的距离
- 距离初始也是赋为无穷
int Dijkstra()
{
memset(d, 0x3f, sizeof d);
d[1] = 0; // 起点
for(int i = 0; i < n; i ++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
{
if(!st[j] && (t == -1 || d[t] > d[j]))
t = j; // 找到还没有找过的距离最近的点
}
st[t] = true; // 表示找过了，说明该点的最短路已经确定了
for(int j = 1; j <= n; j ++)
{
d[j] = min(d[j], d[t] + g[t][j]); //用找到的最近的点来更新起点到每一个点的距离
}
}
if(d[n] == 0x3f3f3f3f) return -1;
else return d[n];
}堆优化Dijkstra算法
-
时间复杂度是
-
效率与边数有关，一般效率高，但是当m(边数）太大，就不应该使用，改用朴素的Dijkstra算法，适用于 稀疏图
-
用小根堆来存，每次取根节点（距离最近的点）来更新
-
同时使用一个bool数组来判断是否读取过，因为小根堆实现使用 优先队列 ，有可能存入多次同一元素的更新结果（判断只是为了不重复更新，记录多次同一元素，先出来的也是最小的，后面再找一次不会有任何实际操作，所以判断后退出）
int Dijkstra()
{
priority_queue<PII, vector<int>, greater<PII>> heap;
memset(d, 0x3f, sizeof d);
d[1] = 0;
heap.push({d[1], 1});
while(heap.size())
{
auto t = heap.top(); //取最小
heap.pop();
int ver = t.second, dist = t.first;
if(st[ver]) continue; // 比如第一次边权重为3 第二次重边的权重是2， 第一次三会在遍历时进到堆里，第二次2也会满足条件进到堆里，但是结果是2的先出
else st[ver] = true; // 没找过的 找到后标记找过
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] > dist + w[i])
{
d[j] = dist + w[i];
heap.push({d[j], j}); // 初始d无穷，全部都进，之后进队要求有更新
}
}
}
if(d[n] == 0x3f3f3f3f) return -1;
return d[n];
}边权有负数:
Bellman-Ford算法(DP)
-
时间复杂度是
-
n 次 m 条边
-
能解决经过边数有所限制的问题
-
松弛操作
- 对比 每个点到起点的距离 和 经过当前最近点 再加上 最近点到该点的距离
- 判断哪个近，做更新（和Dijkstra一样
-
三角不等式
-
负环
- 有负环则做不了最短路（在要找的路径上）
- 可以有 循环 n 次， 即找了n条边，如果在n个结点中找一个点的最短路时找了n条边，即起点到该点的最短路出现了大于 n - 1 的数，就证明路径上出现了负环（bellman -ford算法每次找最短距离，此时能找出多于 n - 1的边数，证明在找时经过最小路径的重复，重复后还能是最短路径，证明回路总权重是负值）
-
迭代的含义
- 第一个循环决定了迭代次数，迭代n次就是找到不超过k条边的最短路径
int bellman_ford()
{
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i = 0; i < k; i ++)
{
memcpy(backup, d, sizeof d); //复制上一次的d给backup数组
for(int j = 0; j < m; j ++) // 每次遍历所有边
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w; // 用结构体存每条边
d[b] = min(d[b], backup[a] + w); // 更新距离
//用的是上一次的d，这样保证了找的是经过小于等于 i 的边的最短距离
// 否则会更新为Dijkstra一样的最短距离，如第一次更新 1-3距离更新为 1-2-3 距离，这样超出了i条边
}
}
return d[n];
}
if(d[n] > 0x3f3f3f3f / 2) false; // 意思是，n结点的数可能被改了，但是按题目范围不能改太多
//所以用这个判断SPFA算法
-
时间复杂度一般是 , 最坏是
-
无法解决经过边数有限的问题
-
其实可以用来写 Dijkstra算法的题，而且更快，但是当 nm 过大时，不用
-
使用邻接表
-
其实是对bellman算法的优化，判断结点
d[a]是否有更新，有才更新其所连接的结点 -
使用队列存储更新的结点，在一次更新中重复存储一个结点没有意义，其距离会在更新中选择最短的距离，所以存多次的每次更新都一样，所以不用存
#include <queue>
void spfa()
{
memset(d, 0x3f, sizeof d);
d[1] = 0;
q.push(1);
st[1] = true;
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] > d[t] + w[i]) // 是否更新
{
d[j] = d[t] + w[i];
if(!st[j]) // 判断是否加进队了，如果加进去了就不用再加一次，但是其距离的更新还是要更新的
{
q.push(j);
st[j] = true;
}
}
}
}
if(d[n] > 0x3f3f3f3f / 2) cout << "NO" << endl;
else cout << d[n] << endl;
}多源汇最短路
很多起点到多终点的最短路
Floyd算法
- 时间复杂度
- 暴力三重运算，基于动态规划
- 找 i 到 j 的最短距离，从 i 出发，找所有点，看 i 到 k 的距离 + k 到 j 的距离 是否会小于 i 经过 小于等于 k - 1 个点，到 j 的距离
- k的循环相当于找经过k个点的结果
[[include]] <iostream>
[[include]] <cmath>
int d[N][N]; //邻接矩阵，先存下所有边
//邻接阵初始化
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF; //无穷
void floyd()
{
for(int k = 1; k <= n; k ++) //先用k点来看所有经过k点的点
for(int i = 1; i <= n; i ++) //i点 经过 k 点到达目的点
for(int j = 1; j <= n; j ++) // 经i点的点到达所有点的距离更新
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}