最短路问题
dijkstra算法
用于解决无负权边的单源最短路问题
朴素版：时间复杂度O(n^2)，适用于稠密图，优点比较好写，缺点n较大时会T，我们使用邻接矩阵来存图，用g[x][y]记录从x到y的边权，用dis[x]代表从源点到x的最短路，核心在于贪心策略，找源点出发所有边权的最小值，那么可证得此点的最短路一定为该边权值，那么将该点标记，再以此点作为源点，一直找寻更新下去，直到全部点都被标记为止，模板：
#include<bits/stdc++.h> using namespace std; const int N = 2005; int n,m; int g[N][N],dis[N],mk[N]; void dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1] = 0; for(int i = 1;i <= n;i++){ int mx = 0x3f3f3f3f,idx; for(int j = 1;j <= n;j++){ if(!mk[j]&&dis[j] < mx){ mx = dis[j]; idx = j; } } mk[idx] = 1; for(int j = 1;j <= n;j++) if(dis[j] > dis[idx]+g[idx][j]) dis[j] = dis[idx] + g[j][idx]; } return; } int main(){ scanf("%d%d",&n,&m); memset(g,0x3f,sizeof(g)); for(int i = 1;i <= m;i++){ int x,y,v; scanf("%d%d%d",&x,&y,&v); g[x][y] = g[y][x] = min(g[x][y],v); } dijkstra(); if(dis[n] >= 0x3f3f3f3f) printf("-1"); else printf("%d",dis[n]); return 0; }
堆优化版：我们会发现朴素版在n较大的情况下数组内存和时间复杂度都会极大，那么就需要进行优化，我们发现找寻从源点出发的边权最大值的时间复杂度为n，这显然是不优的，这时候我们想到可以用优先队列（堆）——priority_queue将此过程优化为logn，而我们又发现此时仅优化这一过程是用处不大的，因为在比对过程中它的时间复杂度仍然为n，那么怎么办呢？我们联想到之前学过的链表，所以使用邻接表来储存双点间的最短路，那么此时查询的时间复杂度就变为了理想状态下O(m/n)，这个值一般是不大的，近似于log级别，更好的情况下近似于O(1)，此时外层循环枚举的是队列元素，最多有m个，所以我们整体的时间复杂度就优化为了O(mlogn)，这个就很万能了，但是受限于dijkstra算法策略的缺点，它仍不能解决边权为负值的情况，模板：
#include<bits/stdc++.h> using namespace std; const int N = 1000005,M = 5000005;//数组要开大一些，不然会T，why？ int n,m; int hd[N],ver[M],nxt[M],val[M],dis[N],mk[N]; int idx,s; struct node{ int idx,v; }; priority_queue <node> q; bool operator < (const node &x,const node &y){//重载运算符，用于排序结构体时的优先队列 return x.v > y.v; } void add(int x,int y,int v){ ver[++idx] = y; val[idx] = v; nxt[idx] = hd[x]; hd[x] = idx; } void dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1] = 0; q.push((node){1,0}); while(q.size()){ node t = q.top(); q.pop(); if(mk[t.idx]) continue; mk[t.idx] = 1; for(int i = hd[t.idx];i;i = nxt[i]){ int y = ver[i]; if(!mk[y]&&dis[y] > dis[t.idx]+val[i]){ dis[y] = dis[t.idx]+val[i]; q.push((node){y,dis[y]}); } } } } int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= m;i++){ int x,y,v; scanf("%d%d%d",&x,&y,&v); if(x == y) continue; add(x,y,v); add(y,x,v); } s = 1; dijkstra(); printf("%d",dis[n]); return 0; }
SPFA算法
可用于解决几乎所有单源最短路，尤其是边权有负值时
此算法的理论依据是三角不等式（czls所言），也就是当dis[i][l]+dis[k][j] > dis[i][j]时，我们将其更新为较小值，二维数组肯定是会炸空间的，所以我们也用邻接表来储存边，不过经过一些推导我们很快就发现，在一次暴力遍历（枚举全部边）中，我们最多只能确保1个点被更新为了全局最值，那这就很麻烦了，时间复杂度直接变为了O(mn)，怎么省略掉那些无意义的枚举呢？我们联系上述的dijkstra算法的思想，每次当我们找到并更新一个点的最小值时，只有它的邻点可能会被更新，所以我们以此点为中心扩散枚举它的所有邻点，用队列来实现这个效果，每次找到更小值时我们将它的所有邻点存在队列里（类似于广搜），时间复杂度在O(m)：链 到O(mn)：菊花图或者网格图 之间，相较于dijkstra它的优势在于可以解决边权为负的情况，模板：
#include <iostream> #include <queue> #include <cstdio> using namespace std; const int N = 2010, M = 100010; int hd[N], ver[M*2], dis[N], val[M*2], nxt[M*2], mk[N], idx, n, m; void add(int x, int y, int v) { ver[++idx] = y; val[idx] = v; nxt[idx] = hd[x]; hd[x] = idx; } void spfa() { memset(dis, 0x3f, sizeof(dis)); dis[1] = 0; queue <int> q; q.push(1); mk[1] = 1; while (q.size()) { int t = q.front(); q.pop(); mk[t] = 0; for (int i = hd[t]; i; i = nxt[i]) { int y = ver[i], v = val[i]; if (dis[y] > dis[t]+v) { dis[y] = dis[t]+v; if (!mk[y]) q.push(y), mk[y] = 1; } } } } int main () { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int x, y, v; scanf("%d%d%d", &x, &y, &v); add(x, y, v); add(y, x, v); } spfa(); if (dis[n] == 0x3f3f3f3f) printf("-1\n"); else printf("%d\n", dis[n]); return 0; }
弗洛伊德Floyd算法
用于解决多源最短路问题
我们发现上述两个方法都只能解决单源最短路问题，而要使用上述方法解决多源最短路，时间复杂度就要再套上一个n^2，这时候显然就爆了，那么就到了Floyd出场的时候了，这个算法思想很简单，基本上就是暴力枚举，具体实现方法类似于区间dp，核心代码如下：
void floyd(){ for(int k = 1;k <= n;k++) { for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if (dis[i][j] > dis[i][k]+dis[k][j]) dis[i][j] = dis[i][k]+dis[k][j]; } } } }
总结：这几个算法各有利弊，有各自的适用情况，具体运用要结合数据范围及题目要求，灵活使用