最短路算法总汇
约定:图是有向图,n表示图中结点的数量,m表示图中边的数量。
1.dijkstra(朴素版本)
朴素版本的dijkstra算法适用于边数远远多于点数的图中,并且图中不能带有负环。算法思想是贪心思想。
时间复杂度:O(n^2),用邻接矩阵来存储图。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra() {
memset(dist, 0x3f, sizeof dist); //初始化结点dist数组,使1->i的距离都为INF
dist[1] = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j; //找到1->j的最短未访问过的结点
}
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]); //更新1->j的最短距离
}
st[t] = true;
}
if (dist[n] == INF)return -1;
return dist[n];
}
int main()
{
memset(g, 0x3f, sizeof g); //初始化邻接矩阵,使每一条边的长度为INF
scanf("%d%d", &n, &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); //存储下a->b的最小边
}
int res = dijkstra();
cout << res << endl;
return 0;
}
2.dijkstra(堆优化版本)
dijkstra朴素版本中的第二层循环就是找到1->j的最小距离,然后用这个距离去更新其他结点的距离。这里我们可以用小根堆来存储1->j的最小距离。优化版的dijkstra算法适用于结点数与边数相当的无负环图中。
时间复杂度:O(mlog(n)),用链表存储每个结点之间的关系。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const int N = 100010, M = 2 * N;
int n, m;
int h[N], ne[M], e[M], w[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dijkstra() {
memset(dist, 0x3f, sizeof dist); //初始化结点dist数组,使1->i的距离都为INF
priority_queue<PII, vector<PII>, greater<PII>> help; //定义小根堆
dist[1] = 0;
help.push({ dist[1],1 }); //这里pair<int,int>中first一定要是dist,因为排序是要以dist的大小排序,而pair的排序规则是优先first
while (help.size()) {
auto t = help.top(); //取堆顶元素
help.pop(); //删除堆顶元素
int ip = t.second;
if (st[ip])continue; //如果该结点被遍历过就跳过
st[ip] = true;
for (int i = h[ip]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[ip] + w[i]) {
dist[j] = dist[ip] + w[i]; //当1->j的距离大于 1->ip->j的距离时更新1->j的距离
help.push({ dist[j],j });
}
}
}
if (dist[n] == INF)return -1;
return dist[n];
}
int main()
{
memset(h, -1, sizeof h); //初始化头结点数组为-1
scanf("%d%d", &n, &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c); //存储结点之间的关系
}
int res = dijkstra();
cout << res << endl;
return 0;
}
3.bellman-ford
bellman-ford算法适用于有重边和自环的图,算法枚举每一步的时候通过枚举更新1->j的最短距离。
时间复杂度:O(k*m)(k表示最长步数),用结构体来存储结点之间的关系。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 510, M = 100010;
int n, m, k;
int dist[N], backup[N];
struct EDG {
int a, b, w;
}edg[M];
int bellman_frod() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, dist, sizeof dist); //复制dist数组的值到backup中
int a, b, c;
for (int j = 0; j < m; j++) {
a = edg[j].a, b = edg[j].b, c = edg[j].w;
if (dist[b] > backup[a] + c) {
dist[b] = backup[a] + c;
}
}
}
if (dist[n] > INF / 2)return INF; //因为存在负权边所以dist数组不一定都为INF
return dist[n];
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edg[i] = { a,b,c };
}
int res = bellman_frod();
if (res == INF)puts("impossible");
else printf("%d", res);
return 0;
}
4.spfa
spfa算法作为bellman_ford的优化版本,用到的优化手法是队列优化。用到的思想也是动态规划的思想。能解决的图论问题更是十分广泛,几乎dijkstra能解决的spfa也能解决。所以需要重点理解
时间复杂度:O(k*m)(k是常数),存储图的方式是邻接表。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 100010, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int spfa() {
memset(dist, 0x3f, sizeof dist); //初始化1->i的距离为INF
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size()) {
auto t = q.front(); //取队头元素
q.pop(); //删除队头元素
st[t] = false; //将不在队列中的结点标记为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]; //如果1->j的距离大于1->t->j的距离就更新1->j的距离
if (!st[j]) { //如果结点j不在队列中就加入队列
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] > INF / 2)return INF;
return dist[n];
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int res = spfa();
if (res == INF)puts("impossible");
else printf("%d", res);
return 0;
}
5.Floyd
Floyd适用于多源最短路问题,其用到的思想是动态规划。
时间复杂度:O(n^3),存储图用邻接矩阵
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 210;
int n, m, k;
int g[N][N];
void floyd()
{
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]); //这里g[i][j]是i->j的最短距离
}
}
}
}
int main()
{
scanf_s("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = INF;
if (i == j)
g[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
scanf_s("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
floyd();
while (k--) {
int a, b;
scanf_s("%d%d", &a, &b);
if (g[a][b] > INF / 2)puts("impossible");
else printf("%d\n", g[a][b]);
}
return 0;
}