图论-五种最短路算法
- 基础算法
- 2024-08-26
- 433热度
- 0评论
一、最短路是什么？
最短路径： 从某个点A（位置）到另一个点B(位置)的最短距离，实现方法：点A途中可以经过很多个点C，然后通过不断更新点A到途中点 C 的最短距离，最后实现最短距离到达 点B。
A -> C1 -> C2 -> C3 -> B
最短路径的分类：
单源最短路：图中的一个点到其余各点的最短路径
多源最短路：图中每两个点的最短路径
框架图解：（如果看不清的话，放大浏览器再观看）
图中稠密图用邻接矩阵，稀疏图用邻接表
二、朴素Dijkstra算法
Dijkstra算法（迪杰斯拉算法）：该算法的特点是从起始点开始，采用贪心算法的策略，采用加点的的方式，每次遍历到起始点距离最近且从未被访问过的顶点的邻接节点t，将该点t加入集合S中，直到扩展到终点位置。
时间复杂度：O（n ^ 2）
思想（操作）：
-
将图上的点分为两个集合：分别是S集合和N集合
-
S：表示访问过的点（用st数组存储）
-
N：表示未访问过的点
-
-
将N集合中的点按到S集合距离最短依次加入到S集合中
-
用刚到S集合中的点t去更新集合N到起始点的距离（这一步也就是松弛操作）
图解：
步骤： dist[ ]：每个点到起始点的距离 st[ ]：是否加入到了s集合中
-
初始化距离：把每个点都初始化为0x3f3f3f3f（无穷大）
-
进行n层循环：遍历dist数组，找到一个不在S集合中并距离S集合最短的点t，每一层循环都将找到的点t将它放入S集合中（st[t] = true）
-
用找到的点t去更新N集合到起始点的距离（松弛操作）
代码 + 注释：
const int N = 1e5 + 10;//多少个点
int dist[N]; //每个点到起始点的距离
bool st[N]; //S集合
void dijkstra(){
memset(dist, 0x3f3f3f3f, sizeof dist);//初始化距离
dist[1] = 0;
for(int i = 1; i <= n; i ++){ //进行n次循环
int t = -1; //设找到的点初始化为1
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[j] < dist[t]))
//如果该点j没在S集合中并且没更新或者有距离S集合更小的点
t = j; //找到该点
}
st[t] = true;加入集合S中
//松弛操作，用该点更新到s的距离
for(int j = 1; j <= n; j ++){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) puts("impossible");//如果为无穷大说明到不了n点
else printf("%d", dist[n]);
} 三、堆优化版Dijkstra算法
堆优化版Dijkstra算法：堆优化版Dijkstra算法是对朴素Dijkstra算法遍历所有点比较找出距离最近的点这一步骤，使用小根堆（优先队列）对这段代码进行优化：
for(int i = 1; i <= n; i ++){ //进行n次循环
int t = -1; //设找到的点初始化为1
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[j] < dist[t]))
//如果该点j没在S集合中并且没更新或者有距离S集合更小的点
t = j; //找到该点
} 时间复杂度：O（m * logn）
思想： typedef pair<int, int>PII;
用小根堆priority_queue<PII, vector
步骤：
- 初始化距离：把每个点都初始化为0x3f3f3f3f（无穷大），并将1号点放在堆中
- 取出堆顶的点，用该点t进行拓展，采用邻接表的数据结构，遍历该点t能到的所有节点
- 进行松弛操作，然后把松弛的点和距离加入堆中。
代码 + 注释：
typedef pair<int, int>PII; //pair<int, int>用来存两个值
const int N = 1e5 + 10;
int dist[N];
bool st[N];
int dijkstra(){
memeset(dist, 0x3f3f3f3f, sizeof dist);//初始化距离
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<int>>heap;//定义小根堆
heap.push({0, 1}); //一定要距离在第一位，因为小根堆是根据第一个数据来排序
while(heap.size()){
PII t = heap.top(); //取堆顶距离最小的元素
heap.pop();
int distance = t.first, ver = t.second;//取出距离和点
if(st[ver]) continue;//如果该点以及加入了集合S中，就continue
st[ver] = true; //否则加入该点
for(int i = h[ver]; i != -1; i = ne[i]){ //遍历该点能到的点的位置
int j = e[i];
if(dist[j] > distance + w[i]){ //进行松弛操作
dist[j] = distance + w[i];
heap.push({dist[j], j}); //入堆
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}四、Bellman_Ford算法
Bellman_Ford算法(贝尔曼-福特算法)：该算法比Dijkstra算法更具有普遍性，Dijkstra算法采用的是贪心思想，而Bellman_Ford采用的是动态规划，因为它对边没有要求，可以处理负权边与负权回路，也可以求边数限制的最短路，缺点是它的时间复杂度比较高，不能判断负环
时间复杂度：O（n * m）
思想：用结构体来存储图，对所有的边（重点）进行n - 1轮松弛操作，就是第一轮对所有边进行松弛，得到的是源点最多经过一条边到达其他顶点的最短距离，第二轮对所有的边进行松弛，得到的是最多经过两条边到其他顶点的最短距离，以此类推，最后达到n**点**
图解：
步骤：
- 循环n - 1次，每次循环更新每条边的最短距离
- 备份一份上次迭代dist距离的数据，防止串联
- 用以后的dist[j]进行拓展，松弛操作
代码 + 注释：
const int N = 1e5 + 10;
int dist[N];//距离
int back[N];//备份的数据
struct Edge{
int a, b, w;
}edge[N];
int bellman_ford(){
memset(dist, 0x3f3f3f3f, sizeof dist); //初始化距离
dist[0] = 1;
for(int = 0; i <= k; i ++){ //可以求只经过k条边（限制边数）
memcpy(back, dist, sizeof dist); //备份防止串联
for(int j = 1; j <= n; j ++){ //遍历每个点
int a = edge[i].a, b = edge[i].b, w = edge[i].w; //取值
dist[b] = min(dist[b], back[a] + w); //松弛操作
}
}
if(dist[n] > 0x3f3f3f3f / 2) return -1; //因为存在负权边，所以0x3f3f3f3f要除2
return dist[n];
} 五、spfa算法
SPFA算法（全称Shortest Path Faster Algorithm）：是Bellman_frod的队优化形式，通常用来求含负权边的的单源最短路问题，以及判断负权环，如果存在负权环就不能用SPFA算法计算最短路
SPFA算法与Bellman_frod的区别：SPFA是Bellman_ford的队优化版，但Bellman_Ford可以用来求负环的最短路，是因为其循环次数是有限制的，因此不会发生死循环，而SPFA算法不可以求带有负环的最短路，由于用了队列存储，只要发生了更新就会不断的入队，因此有了负权回路就不能用SPFA否则会死循环，但是SPFA可以利用这点来判断图中是否存在负环，如果某个点（非终点）的经过边数达到了n就说明存在负环。
时间复杂度：由于SPFA是Bellman_ford优化而来，所以SPFA的最坏的情况是O(n * m)，一般情况下是O（n）
对Bellman_ford的代码优化：
for(int j = 1; j <= n; j ++){ //遍历每个点
int a = edge[i].a, b = edge[i].b, w = edge[i].w; //取值
dist[b] = min(dist[b], back[a] + w); //松弛操作
}思路：采用的是类似BFS无权环的思路，设立一个队列来保存待优化的结点，优化时每次取队头结点t，然后遍历队头能经过的边到达的点v，t点对所能经过的边的点v进行松弛操作，如果能进行松弛操作，并且v点不在当前队列中，就将v点入队，这样不断进行松弛操作，直到队列为空为止
步骤：
- 初始化dist[ ]数组，建立一个队列，将起始点入队
- 取出队头进行扩展，并进行松弛操作
代码 + 注释：
const int N = 1e5 + 10; //多少个点
int e[N], ne[N], w[N], idx, h[N];
void add(int a, int b, int c){ //邻接表的存储方式
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
int spfa(){
memset(dist, 0x3f3f3f3f, sizeof dist); //初始化距离
dist[0] = 1;
queue<int> q; //定义队列
q.push(1);
st[1] = true;
while(q.size()){
int t = q.front(); //取出队头
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){ //遍历t能到的点
int j = e[i];
if(dist[j] > dist[t] + w[i]){ //松弛操作
dist[j] = dist[t] + w[i];
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}SPFA算法判读负环的代码 + 注释：
const int N = 1e5 + 10;
int dist[N];
int cnt[N];记录当前点t到源点最短路的边数，
bool spfa(){
// 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新
queue<int>q;
//不仅仅是第一个点了， 因为第一个点可能到不了有负环的点， 因此把所有点都加入队列
for(int i = 1;i <= n; i ++){
q.push(i);
st[i] = true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;//如果能进行松弛操作就在当前点的cnt+ 1
if(cnt[j] >= n){
return true;
}
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}六、Floyd算法
Floyd算法（弗洛伊德算法又称插点法）：采用动态规划的思想，来解决给多源最短路的问题，可以求图中的任意一点x到任意一点y的距离
时间复杂度：O(n ^ 3) 三重循环
算法思路：从图的带权邻接矩阵开始，进行n次迭代更新，每次更新每两个点之间的最短距离，状态方程：f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
步骤：
- 初始化：从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
- 对于每一对顶点 i 和 j, 看看是否存在一个顶点 k 使得从 i 到 k 再到 j 比已知的路径更短。如果是更新它。
代码 + 注释：
void Folyd(){
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;
}
}
//动态规划
for(int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}