基础图论之最短路
朴素版的Dijkstra算法
- 稠密图：数据范围 m~n^2 （m = 1e5, n = 500)，复杂度n^2，邻接矩阵存图
- 解题思路：外层迭代 n 次，每次确定一个点的最短路，st[i] 表明当前已确定最短距离的点，确定最短距离的点 t 之后，用 t 更新其他点的距离。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n, m;
int g[N][N]; //稠密图用邻接矩阵存，稀疏图用邻接表存
int dist[N]; //表示从1号点到该点的当前的最短路
bool st[N]; //判断该点的最短路是否已经确定
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i ++) //迭代n次，每次确定一个点的最短路
{
int t = -1;
for(int j = 1; j <= n; j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j])) //如果当前的t不是最短的，更新为j
t = j;
st[t] = true; //表明t已经完成最短路径
for(int j = 1; j <= n; j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]); //用t更新到点j的最短路径，即一号点到t的距离+t到j的距离
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c); //该题会有重边，只需取边权最小的一条边
}
int t = dijkstra();
cout << t << endl;
return 0;
}堆优化版的Dijkstra算法
- 稀疏图：数据范围 m~n （m = 1e5, n = 1e5)，复杂度mlogn，邻接表存图
- 解题思路：遍历每条边，如果dist[j] > distance + w[i]， 则更新到点 j 的距离，队列维护点 j 以及从源点到点 j 的最短距离，遍历边的时间复杂度 m ，在优先队列中更新一个点的时间复杂度为 logn，总时间复杂度为 mlogn，st[i]含义同上。
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e6+10;
typedef pair<int, int> PII;
int n, m;
int h[N], e[N], ne[N], w[N], idx; //w[N]记录权重
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 dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII> >heap;
heap.push({0, 1}); //前一个数表示距离，后一个数表示编号，此时将编号唯一的点加入队列
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];
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];
}
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 = dijkstra();
cout << t;
return 0;
}Bellman_ford算法
- 时间复杂度：O(mn) ,外层 k（k~n)个循环,确定从1号点到n号点的最多经过k条边的最短距离，内从每次遍历m条边。
- Bellman_ford算法着重解决有边数限制的最短路。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 100010;
int n, m, k;
int dist[N], backup[N];
struct Edge
{
int a, b, w;
}edge[M];
int Bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= k; i ++) //遍历k次，从1号点到n号点的最多经过k条边的最短距离
{
memcpy(backup, dist, sizeof backup);
//跟前几个不同的是，该题有边数限制，不能时时用前一个点的距离去更新后一个点的距离
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);
//例：当j为1时，此时dist[2]=1,求dist[3]时，不能用dist[2]去更新到点3的距离，因为题中要求只经过一条边，此时只能用dist[1]去更新距离，
//也即backup[1]+w,假如题中要求两条边，则会重新将dist[2]的值赋值给backup[2],此时再求dist[3]是就可用dist[2]更新，即backup[2]+w
}
}
if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible";
else cout << dist[n];
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= m; i ++)
{
int a, b, w;
cin >> a >> b >> w;
edge[i] = {a, b, w};
}
Bellman_ford();
return 0;
}SPFA算法
- SPFA算法 是对 Bellman_ford 算法的优化，后者会遍历所有的边，因此会有很多无意义的更新，而我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新，该节点才会得到更新，因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。
- spfa可以判断负环，因为只要距离更新就会有元素入队，可以用一个cnt数组记录每个点到源点的边数，一个点被更新一次就+1，一旦有点的边数达到了n，就证明存在负环。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int w[N], ne[N], h[N], e[N], idx;
bool st[N];
int dist[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void 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; //从队列中取出来之后该节点st被标记为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])
{
q.push(j);
st[j] = true;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) cout << "impossible";
else cout << dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
spfa();
return 0;
}Floyd算法
- Floyd 算法着重解决多源最短距离，时间复杂度 O(n ^ 3)
#include<iostream>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, q;
int d[N][N];
void floyd()
{
//从 i 到 j 经过点 k 的距离
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]); //从 i 到 k 的距离 + 从 k 到 j 的距离
//f[i, j, k] = min(f[i, j, k - 1], f[i, k, k - 1] + f[k, j, k - 1])
}
int main()
{
cin >> n >> m >> q;
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;
}
}
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(d[a][b] > INF / 2) cout << "impossible" << endl;
else cout << t << endl;
}
return 0;
}
注意事项和区别
https://www.acwing.com/file_system/file/content/whole/index/content/369161/
为什么Dijkstra不能使用在含负权的图中？
https://www.acwing.com/solution/content/6320/
标签：图论,dist,idx,int,短路,基础,st,include From： https://www.cnblogs.com/breeze-ku/p/17087802.html