0%

单元最短路问题概述

单元最短路是在图论中求两个单元(节点)之间边权值和最小的一个方案。

1

通常使用“松弛”来解决此类问题。
对于节点A,B:如果使AB中间增加中转节点C,那么:如果AC+CB权值和小于AB的权值,则AB的更短距离为AC+CB的距离
如此反复,直到保证任意两点之间都求出最短权值和为止

在程序中通常像这样实现:

1
2
3
4
5
for(...) {  //遍历节点
if (weight[i][j] > weight[i][x] + weight[x][j]) { //x作为中转节点
dis[i][j] = weight[i][x] + weight[x][j] //用中转节点松弛
}
}

2 Floyed算法

一个复杂度为O(N^3)的多元最短路径算法算法
原理是直接枚举所有的起点,终点,以及它们之间的中转点并不断的尝试松弛操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

int G[1003][1003], dis[1003][1003];

int main () {
std::ios::sync_with_stdio(false);
int i, j;
int n, m, s, f, g, w, x, y;
std::cin >> n >> m >> s;

for (i = 1; i <= n; ++ i) {
for (j = 1; j <= n; ++ j) {
dis[i][j] = 2147483647;
}
}

for (i = 1; i <= m; ++ i) {
std::cin >> f >> g >> w;
G[f][g] = dis[f][g] = w;
}

for (int k = 1; k <= n; ++ k)
for (i = 1; i <= n; ++ i)
for (j = 1; j <= n; ++ j)
if (G[i][j] > G[i][k] + G[k][j]) dis[i][j] = G[i][k] + G[k][j];

dis[s][s] = 0;
for (i = 1; i <= n; ++ i) std::cout << dis[s][i] << ' ';

return 0;
}

3 SPFA算法

SPFA借助队列优化,本质也是一个不断松弛的过程
更加适合稀疏图,但是在稠密图面前可能退化到O(VE)的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

struct node {
int u, v, w;
};

std::queue<int> Q;
std::vector<node> v[10001];
int dis[10001], count[10001];
bool inqueue[10001];

void SPFA(int start) {
int temp, temp2, temp3, i;

memset(dis, 127, sizeof(dis));
dis[start] = 0;
++ count[start];Q.push(start);
while(!Q.empty()) {
temp = Q.front();
Q.pop();
inqueue[temp] = false;
for (i = 1; i <= v[temp].size(); ++ i) {
temp2 = v[temp][i].v;
temp3 = v[temp][i].w;
if (dis[temp] + temp3 < dis[temp2]) {
dis[temp2] = dis[temp] + temp3;
if (!inqueue[temp2]) {
Q.push(temp2);
inqueue[temp2] = true;
}
}
}
}
}

int main() {
int m, n, temp, temp2, temp3;
std::cin >> n >> m;
for (int i = 1; i <= m; ++ i) {
std::cin >> temp >> temp2 >> temp3;
v[temp].push_back({temp, temp2, temp3});
}

SPFA(1);

std::cout << dis[n];

return 0;
}