随着2020的即将到来,似乎越来越忙了(hh,当然不是忙于准备年货,而是忙于补各种作业).
今天下午难得有段闲暇时光,复习一下(之前就没理解透透的吧) 图论中的最短路部分,以
便更好的学习.
最短路算法:
1、Dijkstra（一般）: 通过每次循环找全局最小值进行更新其他节点(时间复杂度:O(n^2))
Dijkstra（优化）：通过二叉堆(优先级队列)找最小值(队首如果就是最小值的话,我们就不用每次都去寻找最小值了)
(时间复杂度:O(mlog(n))
2、Bellman-Ford ：(后续补充,先学了SPFA,hhhhh)
3、SPFA(Bellman-ford的优化) : 通过队列(类似于BFS,每个点可能出队、入队多次)来实现每个顶点的更新,直到队列
为空为止.
(时间复杂度(km),其中 k 是一个较小的常数)
4、Floyd（任意两点间的最短路）:
(时间复杂度:O(n^3)
下面逐个介绍一下各个算法及实现代码:
1、Dijkstra：
优点:优化后的算法时间复杂度相对于其他算法来说较低
缺点:无法处理有负边权的图(这是重点),也就是目光短浅,具体怎么短浅稍后细说.
算法流程:
1、初始化dist[1] = 0,(因为本身到自己的距离是 0 ),其余节点的设置为正无穷大(memset(dist,0x3f,sizeof(dist));
2、找出一个**未被标记的**、dist[x]最小的节点 x ,然后标记节点 x.
3、扫描节点 x 的所有出边(x,y,z),也就是所有跟节点 x 相连的边,若dist[y] > dist[x] + z,则使用dist[y] = dist[x] + z进行更新,dist[y].（这里用到了三角不等式的原理）.
4、重复上述2 ~ 3 个步骤,直到所有节点都被更新.
用图来理解更清晰:
具体看这位大佬的图解: https://www.acwing.com/blog/content/462/ （十分详细）
（懒得画了,hhhhhhh）
为啥不能处理负权?
首先我们要清楚一个点:Dijkstra是每次贪心的选择跟当前邻接的点,而不会去考虑处邻接之外的其他点,举个例子来说:
8
A ---- B
| /
| /
10| / -4
| /
C
从 A -- > B 我们可以很明显看出最短路径是 A - > C - > B （10 + （-4）） = 6;
但是通过Dijkstra算法我们得到的结果是 A - > B （8）,答案是 8;
(可以自己试一下)
因为我们从起点 A 开始,最先开始找的是 A -> B 所花费的路径短还是 A -> C 花费的路径短,当到 B (第一次选择的结果,就会从B开始在找与B相关的最短的边)(所以如果我们用Dijkstra来处理有负权值得图时得到得答案很可能是不正确的).
代码部分(一般): 题目链接: https://www.acwing.com/problem/content/851/
（需要修改一下输出才能AC哦）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<string>
#define INF 0x3f3f3f3f // 表示最大值
using namespace std;
const int maxn =505;
int a[maxn][maxn],vis[maxn],dist[maxn]; // 采用邻接矩阵来存图(消耗得内存较大)
int n,m;
int main(void) {
void Dijkstra();
memset(a,0x3f,sizeof(a));
memset(dist,0x3f,sizeof(dist)); // 一定要记得初始化为正无穷大
memset(vis,0,sizeof(vis)); // 标记
scanf("%d%d",&n,&m);
int x,y,w;
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d",&x,&y,&w);
a[x][y] = min(a[x][y],w); // 可能会有重边(重复的边),所以需要取最小值
}
Dijkstra();
for(int i = 1; i <= n; i ++ ){
printf("%d
",dist[i]);
}
return 0;
}
void Dijkstra() {
int x = 0; // 用来记录每次全局最小值得下标
dist[1] = 0; // 刚开始与自身的距离是 0
for(int i = 1; i < n; i ++) { // 循环 N - 1 次(因为起点已经更新了,还剩下 N - 1 个点未更新)
x = 0;
for(int j = i; j <= n; j ++) {
if(vis[j] == 0 && (x == 0 || dist[j] < dist[x])) { // 选取未标记过的全局最小值
x = j;
}
}
vis[x] = 1; // 标记已选中的顶点
for(int j = 1; j <= n; j ++) { // 更新与该顶点相关的边
dist[j] = min(dist[j],dist[x] + a[x][j]);
}
}
return ;
}
Dijkstra(优化) ：（采用邻接表的存储方式来存图(模拟数组链表的方式)）
题目链接: https://www.acwing.com/problem/content/852/
（需要修改一下输出才能AC哦）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 6;
priority_queue<pair<int,int> >pq; //优先级队列默认是从大到小进行排序的(我们每次插入队列中这个数的相反数,自然就能表示这个数的最小值)
int vis[maxn],head[maxn],Next[maxn],edge[maxn],ver[maxn];
int dist[maxn];
int n,m,tot;
int main(void) {
void Dijkstra();
void add(int x,int y,int w);
int x,y,w;
memset(vis,0,sizeof(vis));
memset(dist,0x3f,sizeof(dist));
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
Dijkstra();
for(int i = 1; i <= n; i ++ ){
printf("%d
",dist[i]);
}
return 0;
}
void add(int x,int y,int w) {
ver[++tot] = y,edge[tot] = w; // ver[]:表示每条边的终点,edge[]:表示每条边的权值
Next[tot] = head[x],head[x] = tot; /* Next[]:存储上一条边的序号,用来进行连接(遍历)
插入到表头 表示从相同节点出发的下一条边在ver和edge数组中的存储位置
*/
return ; // head[]:记录从每个节点出发的第一条边在ver 和 edge 数组中的存储位置
}
void Dijkstra() {
dist[1] = 0;
pq.push(make_pair(0,1)); // first:权值大小,second:该权值对应的节点
while(pq.size()) {
int x = pq.top().second;pq.pop();
if(vis[x]) continue;
vis[x] = 1;
// 遍历与该节点相关的所有边(更新)
for(int i = head[x]; i ; i = Next[i]) {
int y = ver[i],z = edge[i];
if(dist[y] > dist[x] + z) {
// 将更新后的最小值(值和对应的节点)组合重新插入到队列中,以便于后面寻找更小的(每次都要是最小距离)
dist[y] = dist[x] + z;
pq.push(make_pair(-dist[y],y));
}
}
}
return ;
}
2、SPFA（）算法:
优点:SPFA()算法最大的优点莫过于可以处理负边权,而且优化过后的时间复杂度与Dijkstra()算法相差不大
缺点:仅用队列实现的SPFA算法时间复杂度还是有点高的,因为它每次顶点可能会多次进行出队、入队、这也就是它可以 处理负边权的最大原因。
算法流程:
1、建立一个队列,最初队列只包含起点 1
2、取出队头节点x,扫描它的所有出边(x,y,z),若dist[y] > dist[x] + z,则使用dist[x] + z更新dist[y].同时，若
y 不在队列中,则把 y 入队,并且进行标记.
3、重复上述步骤,直到队列为空。
该算法的队列都保存了待扩展的节点(这点也很重要,可以拿上面的例子模拟一下).每次入队都相当于完成一次dist数组的更新操作,使其满足三角形不等式.
一个节点可能会出队、入队多次。最终，图中节点收敛到全部满足三角形不等式的状态。
代码部分:
题目链接: https://www.acwing.com/problem/content/853/
（需要修改一下输出才能AC哦）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<string>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
int head[maxn],Next[maxn],edge[maxn],ver[maxn];
int dist[maxn],vis[maxn];
int n,m,tot;
int main(void) {
void add(int x,int y,int w);
void spfa();
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i ++) {
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
spfa();
for(int i = 1; i <= n; i ++) {
cout<<dist[i]<<endl;
}
return 0;
}
void add(int x,int y,int w) {
ver[++tot] = y,edge[tot] = w;
Next[tot] = head[x],head[x] = tot;
return ;
}
void spfa() {
queue<int>q;
dist[1] = 0,q.push(1);
vis[1] = 1;
while(!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0; // 出队后就标记为未使用过
for(int i = head[x]; i ; i = Next[i]) {
int y = ver[i],z = edge[i];
if(dist[y] > dist[x] + z) {
dist[y] = dist[x] + z; // 这里只要符合三角式定理，就更新
if(vis[y] == 0) {
q.push(y); // 每次入队的是未标记过的顶点
vis[y] = 1; // 入队后就标记已使用了
}
}
}
}
return ;
}