#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点)的距离初始化为无穷大inf
for (int i = 0; i <= n; i ++ ) d[i] = inf;
// 修改源点到源点的最短路径, 为0
d[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的最短路径就是0
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;
}
}
// 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;
}
