迪杰斯特拉算法Dijkstra
该算法不能存在负权边
Dijkstra求最短路 I
思路：
- 初始化距离数组, dist[1] = 0, dist[i] = inf;
- for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
- 将不在S中dist_min的点->t
- t->S加入最短路集合
- 用t更新到其他点的距离
更新为其他到起点的最短路径
1、
int g[N][N]; 用g[x][[y]表示x、y之间的距离
int dist[N]; 用于记录每一个点距离第一个点的距离
bool st[N]; 用于记录该点的最短距离是否已经确定
然后开启n次操作，每次操作依次找到节点最短路
2、设第一个点为源点，令dist[1]==0,dist[i]==正无穷（若该点与源点不相连，则距离无穷）
3、
for循环遍历所有点，找到最短距离没有确定的点中的 距离该点最近的点；并用该点更新其他点距离
解析：
（第一次操作）从源点开始找，因为第一个点为源点，所以自己到自己的距离为0，于是找到第一个点成为离源点最近的点；确定了第一个点到源点的最短距离；用该点（一号点）更新到其他点到源点最短距离（二号点距离为2,三号距离4）
4、
解析：
（第二次操作）从上次确定最短距离的点开始找，找距离该点最短的点（二号点）；确定了二号点到源点的最短距离；用该点（二号点）更新其他点到源点最短距离（得三号点距离为3）
5、有n个节点，我们操作n次，最终得到n节点到源点的最短路
核心操作： 找到距离源点最近的节点t，然后用t更新其他节点
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=510; int g[N][N]; //为稠密阵所以用邻接矩阵存储，用g[x][[y]表示x、y之间的距离 int dist[N]; //用于记录每一个点距离第一个点的距离 bool st[N]; //用于记录该点的最短距离是否已经确定 int n,m; int Dijkstra() { memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大 dist[1]=0; //第一个点到自身的距离为0 for(int i=0;i<n;i++) //有n个点所以要进行n次操作 { int t=-1; //t存储当前访问的点，值为-1只是为了标记第一个搜到的节点（因为题目中无负值，-1不会影响结点判断） for(int j=1;j<=n;j++) //从1号点开始遍历 dist 数组，找到没有确定最短路径的节点中 距离源点最近的点t if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; st[t]=true; for(int j=1;j<=n;j++) //找到了距离已经确定最短路的点t，用点t去更新其他的点到源点的距离 dist[j]=min(dist[j],dist[t]+g[t][j]); } if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最短路径 return dist[n]; } int main() { cin>>n>>m; memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径 //所以每个点初始为无限大 while(m--) { int x,y,z; cin>>x>>y>>z; g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边,x到y的距离为z } cout<<Dijkstra()<<endl; return 0; }
时间复杂度分析
寻找路径最短的点：O(n^2)
加入集合S：O(n)
更新距离：O(m)
所以总的时间复杂度为O(n^2)
Dijkstra求最短路 II
思路：最小堆优化
1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为：
弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
用该点更新临界点的距离，若更新成功就加入到堆中。
#include<iostream> #include<cstring> #include<queue> using namespace std; typedef pair<int,int> PII; const int N=1e6+10; int h[N],e[N],ne[N],idx;//数据范围大，稀疏图，邻接表存储 int w[N]; int dist[N];//到源点的距离 bool st[N]; int n,m; void add(int x,int y,int c) { w[idx]=c;//存x到y边长 e[idx]=y;ne[idx]=h[x];h[x]=idx++;//邻接表存储 } int dijkstra() { memset(dist,0x3f,sizeof dist); dist[1]=0; //利用小根堆，根据距离从小到大排序 priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push({0,1});//{距离，节点号}，顺序不能变，pair排序根据先first在根据second排 while(heap.size()) { PII k=heap.top(); heap.pop(); int ver=k.second,distance=k.first;//取节点号 和 源点距离ver的距离 if(st[ver]) continue;//如果距离已经确定，则跳过该点（防止重边） st[ver]=true; for(int i=h[ver];i!=-1;i=ne[i])//更新ver所连接的节点距离 { int j=e[i]; if(dist[j]>distance+w[i])//该点到源点距离>ver到源点距离+ver到该点距离 { dist[j]=distance+w[i]; heap.push({dist[j],j});//只将被更新的点入堆 } } } if(dist[n]==0x3f3f3f3f) return -1; else return dist[n]; } int main() { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int x,y,c; cin>>x>>y>>c; add(x,y,c); } cout<<dijkstra()<<endl; return 0; }
在priority_queue[PII,vector<PII>, greater<PII> > heap;中将返回堆顶
利用堆顶来更新其他点，并加入堆中类似宽搜
贝尔曼-福特算法 bellman-ford
注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];
初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
松弛k次，每次访问m条边
有边数限制的最短路
核心算法：
1、松弛操作
所谓松弛操作，就是看一看dist[v]和dist[u]+u到v的距离哪个大一点。
如果前者大一点，就说明当前的不是最短路，就要赋值为后者，这就叫做松弛。
dist[b]=min(dist[b],dist[a]+w);
每次取出两点以及他们连接的边的权重（a,b,w表示a—>b的一条边）；
用从起点到a的当前最短距离+权重来更新从起点到b的当前最短距离；
2、backup数组
for (int i = 0; i < k; i ++ ) { memcpy(backup, dist, sizeof dist); for (int j = 0; j < m ; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; dist[b] = min(dist[b], backup[a] + w);//dist[b] = min(dist[b], dist[a] + w); } }
backup[j]表示每次进入第2重循环的dist数组的备份；
由题意得k==1，因为有边数限制，所以不能走上面两条边的最短路程2，只能走下路得到最短路程3；
假设没有backup备份数组，虽然只k了一次，但是我们在第一轮松弛操作的时候就可以直接将二三号点的最短距离求出，则得出三号点最短路为2，显然这是错误的
- 使用backup备份数组，防止发生串联更新
memcpy(backup,dist,sizeof dist); dist[b]=min(dist[b],backup[a]+w);
- 用上轮节点2更新的距离--无穷大，来更新节点3， 再取最小值，无穷+1大于无穷，节点3仍然无穷，所以最后更新节点3离起点的距离是3。
总结：利用backup数组保证每次更新只对两点之间的一条边
3、
为什么表示无穷不是 ==
1. if(t==0x3f3f3f3f) puts("impossible"); 2. else cout<<t<<endl;
而是
1. if(t>0x3f3f3f3f/2) puts("impossible"); 2. else cout<<t<<endl;
解析：
如下图所示，4,5号点无法与源点连接，所以距离都是无穷，但是无穷并不都是是标准的0x3f3f3f3f;
由于算法的松弛遍历，最终4号点距离为0x3f3f3f3f,而5号点距离为0x3f3f3f3f-2；
最恶心的情况就是一号点（源点）不相连，其余499个节点相连且距离都为-10000，那么n号点距离为0x3f3f3f3f-499*10000;
而最短路最大距离为500*10000，所以t大于的范围为【500*10000，0x3f3f3f3f-499*10000】 ，显然0x3f3f3f3f/2在其中（即大于这个范围的数会输出“impossible”，而不是输出t值）
（0x3f3f3f3f == 1061109567）
#include<iostream> #include<cstring> using namespace std; const int N=1e5+10; int dist[N],backup[N]; int n,m,k; struct edge { int a,b,w; }edge[N]; int bellman_ford() { memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=1;i<=k;i++) { memcpy(backup,dist,sizeof dist); for(int j=1;j<=m;j++) { int a=edge[j].a,b=edge[j].b,w=edge[j].w; dist[b]=min(dist[b],backup[a]+w); } } return dist[n]; } int main() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; edge[i]={a,b,c}; } int t=bellman_ford(); if(t>0x3f3f3f3f/2) puts("impossible"); else cout<<t<<endl; return 0; }
SPFA算法
Bellman_ford优化：
Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。
该算法不可存在如图负权回路
spfa求最短路
思路：
建立一个队列，初始时队列里只有起始点。
再建立一个数组记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。
再建立一个数组，标记点是否在队列中。
队头不断出队，计算始点起点经过队头到其他点的距离是否变短，如果变短且被点不在队列中，则把该点加入到队尾。
重复执行直到队列为空。
在保存最短路径的数组中，就得到了最短路径。
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[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, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { int t = q.front(); q.pop(); st[t] = false; //如果t变小了，那么t所连接的所有节点都有可能变小 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]) //如果j不在队列中 { q.push(j); st[j] = true; //入队并标记 } } } } return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } int t = spfa(); if (t == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", t); return 0; }
spfa判断负环
思路： 一个通俗易懂的想法
如果存在负环，那么程序就会在环里面一直转永远不会停，因为路径会一直减小
如果不存在负环，有n个节点，那么最短路径长度次数不会超过n-1，因为大于n-1说明有一个点走了至少两次
我们利用cnt[]记录走的边的个数，如果走的边超过n-1那么就有负环
由于可能不是连通图，需要对每个点进行检验，即每个点都入队
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], e[N], ne[N], idx; int w[N]; int dist[N] int cnt[N];//记录每个点到起点的边数，当cnt[i] >= n 表示出现了边数>=结点数，必然有环，而且一定是负环！ bool st[N];//判断当前的点是否已经加入到队列当中了；已经加入队列的结点就不需要反复的把该点加入到队列中了 //就算此次还是会更新到起点的距离，那只用更新一下数值而不用加入到队列当中。 //意味着，st数组起着提高效率的作用，不在乎效率的话，去掉也可以 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, 0x3f, sizeof dist); // dist[1] = 0; // 这里不需要初始化，让dist为0即可，因为有负环dist会不断减小，不断更新 queue<int> q;//用于检测所有点是否有负环 for (int i = 1; i <= n; i ++ ) { //判断负环，只从一个点出发，有可能到达不了负环那里，需要一开始就把所有结点放入队列，且标记进入了队列提高效率 q.push(i); st[i] = true; } while (q.size())//spfa求最短路套路模板 { int t = q.front(); q.pop(); st[t] = false; //更新与t邻接的边 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];//结点j可以通过中间点t降低距离 cnt[j] = cnt[t] + 1;//那么结点j在中间点t的基础上加一条到自己的边 if (cnt[j] >= n) return true;//边数不小于结点数，出现负环，函数结束 if (!st[j])//若此时j没在队列中，则进队。已经在队列中了，上面已经更新了数值。重复加入队列降低效率 { q.push(j);//将被改变距离的结点入队 st[j] = true; } } } } return false;//走到这了，函数还没结束，意味着边数一直小于结点数，不存在负环 } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } if (spfa()) puts("Yes"); else puts("No"); return 0; }
Floyd
算法不能应用于负权回路
Floyd求最短路
基于动态规划思想
算法模板：
void floyd() { 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]); }
记忆： k表示阶段，最外层；取i到j不经过k这个节点和经过k这个节点最短路
#include<iostream> #include<cstring> using namespace std; const int N=210,INF=1e9; int n,m,q; int d[N][N];//d[i][j]表示从i到j的距离 void floyd() { 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]); } int main() { cin>>n>>m>>q; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)//初始化距离数组d if(i==j) d[i][j]=0;//如果是自己到自己则距离为0，否则无穷 else d[i][j]=INF; while(m--) { int a,b,c; cin>>a>>b>>c; d[a][b]=min(d[a][b],c); } floyd(); while(q--) { int a,b; cin>>a>>b; int t=d[a][b]; if(t>INF/2) puts("impossible"); else cout<<t<<endl; } return 0; }
