算法板子：最短路问题——包含朴素Dijkstra算法、堆优化版的Dijkstra算法、SPFA算法、Floyd算法

1. 几种算法的用途

2. Dijkstra算法——求源点到其他所有点的最短路径(不能处理负边权)

（1）朴素Dijkstra算法——适用于稠密图

#include <iostream>
#include <cstring>
using namespace std;const int N = 500 + 10;
int n, m;// 这道题边的条数接近于顶点数量的²，边多是稠密图，用邻接矩阵g来存图; 如果一个图有n个节点，那么邻接矩阵的大小就是n*n
int g[N][N];// d[i]代表源点s到i号点的最短路径; 比如d[4]=3代表源点到点4的最短路径为3
// inf代表int值的无穷大
int d[N], inf = 0x3f3f3f3f;
// vis数组标识某个点是否出圈; vis[4]=0代表节点4没有出圈
int vis[N];// 传入源点s，计算出各个点到源点s的最短路径
int dijkstra(int s)
{// 先将源点到所有点(包括0点)的距离初始化为无穷大inffor (int i = 0; i <= n; i ++ ) d[i] = inf;// 修改源点到源点的最短路径, 为0d[s] = 0;for (int i = 1; i < n; i ++ ){int u = 0;// u保存圈内离源点最近的点for (int j = 1; j <= n; j ++ )if (!vis[j] && d[j] < d[u]) u = j;// 将找到的最近的点u出圈vis[u] = 1;// 更新源点到出圈的点u的邻接点的最短路径for (int j = 1; j <= n; j ++ ){// g[u][j]的值不等于inf代表j是u的邻接点; d[j]代表源点s到点j到的最短路径; d[u]+g[u][j]代表通过u这个点到达点j的路径长度// 对比一下点j是原先的路径更短还是通过点u到达点j是路径更短, 更新源点到点j的最短路径if (g[u][j] != inf) d[j] = min(d[j], d[u] + g[u][j]);}}// 如果源点1到点n的最短路径为无穷大, 说明不存在最短路径if (d[n] == inf) return -1;// 如果最短路径不是无穷大, 说明存在最短路径return d[n];
}int main()
{cin >> n >> m;// 将邻接矩阵每条边的权重都初始化为无穷大memset(g, 0x3f, sizeof g);// 使用邻接矩阵存储图; 若某个点到某个点有边，那么就在对应位置上存上权重，且始终存最小权重for (int i = 0; i < m; i ++ ){int a, b, w;cin >> a >> b >> w;g[a][b] = min(g[a][b], w); }// 因为这道题要算点1到点n的最短路径, 那么源点就可以设置成1, 通过dijkstra算法可以得到源点1到所有点的最短路径, 并在算法的最后返回源点1到点n的最短路径cout << dijkstra(1) << endl;return 0;
}

（2）堆优化版的Dijkstra算法——适用于稀疏图

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 2e5 + 10;
typedef pair<int, int> PII;// 优先级队列q相当于大根堆
// 这里堆顶放的是距离源点最近的点，比如该点距离源点的距离为3，其他点距离源点的距离更大，取相反数后插入堆中，那么距离最近的就是值最大的，放在堆顶
// 堆q每个元素为一个对组，键为源点到该点的最短路径，值是点
priority_queue<PII> q;
// vis标记某点是否已出队，只有未出队的才能更新它的邻接点的最短路径; vis[2]=0代表2这个点未出队
// d[i]代表源点到点i的最短路径
int vis[N], d[N], inf = 0x3f3f3f3f;
// 这道题边比较少，是稀疏图，用邻接表存图; w数组存储权重
int h[N], e[N], ne[N], w[N], idx;int n, m;void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}int dijkstra(int s)
{// 将源点到所有点的最短路径初始化为无穷大for (int i = 0; i <= n; i ++ ) d[i] = inf;// 将源点加入堆d[s] = 0; q.push({-d[s], s});while (q.size()){// 取堆顶; 取出距离源点最近的点auto t = q.top(); q.pop();int u = t.second;// 如果已经出队过，就不能更新邻接点if (vis[u]) continue;// 如果没有出队过，标记它现在已经出队过vis[u] = 1;// 更新该点的邻接点的最短路径for (int i = h[u]; i != -1; i = ne[i]){int j = e[i], c = w[i];// 如果邻接点需要更新，则加入堆中if (d[u] + c < d[j]){d[j] = d[u] + c;q.push({-d[j], j});}}}if (d[n] == inf) return -1;return d[n];
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << dijkstra(1) << endl;return 0;
}

4. SPFA算法——求源点到其他所有点的最短路径、判断是否存在负环(可以处理负边权)

（1）求有负边权的图的最短路径——求源点到其他所有点的最短路径

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 1e5 + 10;int h[N], e[N], ne[N], w[N], idx;
queue<int> q;
int d[N], inf = 0x3f3f3f3f;
// vis[i]代表点i是否在队中; vis[3]=1代表点3在队中, vis[3]=0代表点3不在队中
int vis[N];int n, m;void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}void spfa(int s)
{// 将源点到全部点的最短路径全部初始化为无穷大memset(d, inf, sizeof d);d[s] = 0;// 将源点入队q.push(s); vis[s] = 1;while (q.size()){// 出队队头，标记队头不在队中int f = q.front(); q.pop(); vis[f] = 0;// 更新队头邻接点的最短路径for (int i = h[f]; i != -1; i = ne[i]){int j = e[i], c = w[i];if (d[f] + c < d[j]){d[j] = d[f] + c;// 如果点j不在队中，则加入队中if (!vis[j]) q.push(j), vis[j] = 1;}}}if (d[n] == inf) cout << "impossible" << endl;else cout << d[n] << endl;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}spfa(1);return 0;
}

（2）判断图中是否存在负环(负环指环的权重和为负数)

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 1e5 + 10;
int n, m;int h[N], e[N], ne[N], w[N], idx;
queue<int> q;
// 在图上增加一个虚拟源点，虚拟源点到图中每个点都有条权重为0的边
// cnt数组代表虚拟源点到该点的最短路径的边数; 比如cnt[3]=3代表虚拟源点到点3的最短路径的边数为3
int d[N], vis[N], cnt[N];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}bool spfa()
{// 把所有点加入队列中for (int i = 1; i <= n; i ++ ) q.push(i), vis[i] = true;while (q.size()){int f = q.front(); q.pop(); vis[f] = 0;for (int i = h[f]; i != -1; i = ne[i]){int j = e[i], c = w[i];// 更新源点到点j的最短路径if (d[f] + c < d[j]){// 更新最短路径的长度d[j] = d[f] + c;// 更新最短路径的边数cnt[j] = cnt[f] + 1;// 如果虚拟源点到点j的边数大于等于节点数，则存在负环if (cnt[j] >= n) return true;if (!vis[j]) q.push(j), vis[j] = 1;}}}// 图中不存在负环return false;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << (spfa() ? "Yes" : "No") << endl;return 0;
}

5. Floyd算法——求图中任意两点之间的最短路径(可以处理负边权)

#include <iostream>
using namespace std;const int N = 200 + 10;// d[i][j]代表点i到点j经过节点1~k的最短路径的长度; 例如d[1][3]=2代表点1到点3的最短路径长度为2
int d[N][N], INF = 0x3f3f3f3f;int n, m, k;// 更新两点之间的最短路径
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 >> k;// 处理自环; 图中有可能存在自环，比如点1到点1存在条边，那么点1到点1的最短路径就是0for (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;}}// d可以先看成一个邻接矩阵，存储两点之间边的最小权重for (int i = 0; i < m; i ++ ){int a, b, w;cin >> a >> b >> w;// 图中两点之间可能有重边，保留权重最小的那条边即可d[a][b] = min(d[a][b], w);}floyd();while (k -- ){int a, b;cin >> a >> b;// 如果点a到点b的距离不是无穷大，则存在最短路径; 是无穷大，不存在最短路径; // 这里将无穷大定义为INF/2是因为，就算点a到点b不存在最短路径，但由于存在负边权，有可能使得路径从无穷大变得比无穷大小一些// 所以如果当前点a到点b的路径比无穷大的一半还大，我们就认为两点之间还是无穷大，还是没有最短路径if (d[a][b] > INF / 2) cout << "impossible" << endl;else cout << d[a][b] << endl;}return 0;
}