最短路
源点：起点
汇点：终点
n:图中点数， m:图中边数
重点: 建图
最短路问题不区分有向图和无向图（无向图建两次边）
重边：若两点间存在多条边保留距离最短的
单源最短路
所有边权都是正数
朴素Dijstra算法 O(n^2) ——> 稠密图( m ~ n^2 ) ——> 邻接矩阵
1. 初始化距离, 起点距离为0，其余点初始化为无穷( 表示没有遍历到 )
dist[1] = 0, dist[i] = +∞
2. 循环迭代
s: 所有当前已经确定最短距离的点
// 每次迭代都能确定一个点的最短距离
for i: 1 ~ n
{
不在s中的距离最近的点 ——> t (贪心)
t ——> s
用t来更新其他点的距离
}
算法实现:
int g[N][N]; // 存储每条边
// g[N][N] 初始化: memset(g, 0x3f, sizeof(g));
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 迭代n-1次
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
// 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
// 当前点还没确定最短路 当前的t不是最短的
if ( !st[j] && ( t == -1 || dist[t] > dist[j] ) )
t = j;
st[t] = true;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
// 1->j距离 1->t距离 + t->j的边的长度
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
输入：
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof(g));
while ( m-- ) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min( g[a][b],c ); // 重边时，选取边权最小的
}
堆优化的Dijstra算法 O(mlogn) -> 稀疏图( m ~ n ) -> 邻接表
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边,w存储边权
// memset(h, -1, sizeof(h));
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
void add( int a, int b, int c) {
e[idx] = b, w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
heap.push( { 0, 1 } ); // first存储距离，second存储节点编号
while (heap.size())
{
// 当前距离最小的点
auto t = heap.top();
heap.pop();
// 结点编号，距离
int distance = t.first, ver = t.second;
if ( st[ver] ) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
// 更新最短距离 点i到j的距离
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push( { dist[j], j } );
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
存在负权边
若图中存在负权回路，则可能最短路不存在
SPFA一般优于Bellman-ford，但求解特定问题仍需使用Bellman-ford算法( 如求解不超过k条边的最短路 )
Bellman-ford O(mn)
应用于求解有边数限制的最短路问题
备份防止串联:
有边数限制的最短路
// 迭代k次，表示经过不超过k条边的最短路径
// 1 -> 2 -> ... -> x, 从1到第x个点，若有n条边，说明存在n+1个点，则有两个点编号相同，路径上一定存在环
for k次：
for 所有边(m条) a,b,w // a ——> b (w为边权)
// 更新最短路径
dist[b] = min( dist[b], dist[a] + w ) // 松弛操作
所有边满足：
三角不等式 ——> dist[b] <= dist[a] + w
算法实现:
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
int backup[N]; // backup 表示备份
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径
// 由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
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 );
}
}
if ( dist[n] > 0x3f3f3f3f / 2 ) return -1;
return dist[n];
}
SPFA 一般O(m), 最坏O(mn)
图中不含有负环
大部分含负权的情况都使用SPFA
同样可求解正权边的情况，若无法AC则用Dijstra算法（优化）
/*
SPFA使用BFS进行优化 | dist[b] = min( dist[b], dist[a] + w ) |
只有当a变小时，b才有可能变小，则使用队列来存储所有变小的 a
*/
// 起点放入队列
1 ——> queue
while(队列不空) {
q.front() ——> t // 取出队头
q.pop()
更新t的所有出边 t ——> b (w)
if(b还未被更新) b ——> queue
}
SPFA求最短路
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中，防止队列中存储重复的点
void add( int a, int b, int c) {
e[idx] = b, w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
// 点从队列中出来
st[t] = false;
// 搜索所有出边
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];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
SPFA判断负环 ~ O(mn)
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的边数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 求解是否存在负环，不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
// 负环可能存在于任意点处，初始时将所有点放入队列
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
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];
cnt[j] = cnt[t] + 1; // 边数 + 1
// 如果从1号点到x的最短路中包含至少n+1个点（n条边），则说明存在环
if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
多源汇最短路
Floyd算法 O(n^3)
const int INF = 1e9; // 根据题意
d[i][j] // 邻接矩阵，存储所有的边
初始化：
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; // 判断结果时路径可能比INF小一些
// 算法结束后，d[a][b]表示a到b的最短距离
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 a,b,w;
scanf("%d%d%d", &a,&b,&w);
d[a][b] = min( d[a][b] , w ); // 重边取最小的
输出：
int a,b;
scanf("%d %d", &a, &b );
// 比无穷小一些
if ( d[a][b] > INF / 2 ) cout << "impossible" << endl;
else cout << d[a][b] << endl;
