2X岁，是学生です

0%

最短路算法

发表于 更新于 分类于
本文字数： 5.6k 阅读时长 ≈ 5 分钟

最短路算法

alt

本文时间复杂度中: $n$ 为节点数， $m$ 为边数。

朴素版Dijkstra $O(n^2)$

思路：

从源点开始，先更新与源点间的距离；再找到一个与源点距离最近的点，用这个点作为中继，比较剩余点经该点中继再到源点的距离是否比原来近，近则更新，否则不变，再在剩余的点中查找与源点最近的点，开始下一次循环。

上代码！

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], w[M], idx = 1;
int dist[N];
int n, m;
bool st[N];

void add(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i < n; ++i)//只用循环 n - 1 次（n 个点 n - 1 条边）
    {
        int t = -1;
        for(int j = 1; j <= n; ++j)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j];
            dist[k] = min(dist[k], dist[t] + w[j]);
        }
        st[t] = true;
    }
    if(dist[n] == 0x3f3f3f3f) return -1;//不连通无法更新
    return dist[n];
}

int main()
{
    int x, y, z;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));//注意初始化
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    printf("%d", dijkstra());
    return 0;
}

堆优化版Dijkstra $O(mlogn)$

朴素版 Dijkstra 算法的性能瓶颈在于每次都要在 st 数组中标记为 false 的点中查找dist最小的点；因此可以考虑使用堆来优化。

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
53
54
55
56
57
58
59
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 2e5;
int h[N], e[N], ne[N], w[N], idx = 1;
int dist[N];
int n, m;
bool st[N];

void add(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<PII, vector<PII>, greater<PII>> myheap;//创建小根堆
    dist[1] = 0;
    myheap.push({0, 1});//first存dist，second存节点编号
    while(myheap.size())
    {
        PII temp = myheap.top();
        myheap.pop();
        int curdist = temp.first, curpos = temp.second;
        if(st[curpos]) continue;//可能存在冗余备份，遇到冗余即抛弃
        st[curpos] = true;
        for(int i = h[curpos]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > curdist + w[i])
            {
                dist[j] = curdist + w[i];
                myheap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    int x, y, z;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));//注意初始化
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    printf("%d", dijkstra());
    return 0;
}

由于 Dijkstra 算法只能处理边权为非负数的情况，因此有了下面可以处理负权边的算法。

虽然有负权边，但是不可以有负权回路。

Bellman-Ford算法 $O(m \times n)$ (有边数限制的最短路算法)

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 $1$ 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，输出impossible。

注意：图中可能 存在负权回路。

思路：

$Bellman-Ford$ 算法外层循环循环指定次数 $k$ 次，每次循环都便利所有的边，再利用三角不等式 $dist[epos] \ge dist[spos] + weight$比较并更新 dist。
该算法需要注意防止串联，因此每次循环都要先备份 dist。

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
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 510, K = 510, M = 1e4 + 10;
int dist[N], backup[N];
int n, m, k;
struct  
{
	int l, r, w;
}e[M];

void bellman_ford()
{
	memset(dist, 0x3f, sizeof(dist));
	dist[1] = 0;
	for (int i = 1; i <= k; i++)
	{
		memcpy(backup, dist, sizeof(dist));//备份，防止串联
		for (int j = 1; j <= m; j++)
			if (dist[e[j].r] > backup[e[j].l] + e[j].w)
				dist[e[j].r] = backup[e[j].l] + e[j].w;
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		e[i] = { x,y,z };
	}
	bellman_ford();
	if (dist[n] > 0x3f3f3f3f / 2)
		puts("impossible");
	else
		printf("%d", dist[n]);
	return 0;
}

SPFA算法 一般 $O(m)$，最坏 $O(m \times n)$ (可用于判断是否存在负环)

该算法属于 $Bellman-Ford$ 算法的优化，使用 $BFS$，队列中只放入被更新过后 dist 变小的点编号。

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
53
54
55
56
57
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], w[M], idx = 1;
int dist[N], myq[N];
bool st[N];//这里st数组的含义不同，表示当前点是否在队列中
int n, m;

void myadd(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

int spfa()
{
    int l = 0, r = 1;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0, myq[l] = 1, st[1] = true;
    while(l != r)
    {
        int t = myq[l++];
        if(l == N) l = 0;
        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])//不在队列中则放入队列
                {
                    myq[r++] = j, st[j] =true;
                    if(r == N) r = 0;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        myadd(x, y, z);
    }
    int res = spfa();
    if(res == 0x3f3f3f3f) puts("impossible");
    else printf("%d", dist[n]);
    return 0;
}

若用于判断负环存在性

因为负环存在时，一定不存在最短路，程序会死循环。因此记录一下各个点被访问到的序号，一出现某点被访问到的序号大于总点数，表明存在负环，返回退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//部分代码
    dist[1] = 0, cnt[1] = 1;
...
    if(dist[e[i]] > dist[t] + w[i])
    {            
        dist[e[i]] = dist[t] + w[i];
        cnt[e[i]] = cnt[t] + 1;
        if(cnt[e[i]] > n)//存在负环
            return true;
        if(!st[e[i]])
        {
            myq.push(e[i]);
            st[e[i]] = true;
        }
    }

Floyd算法 $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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 210, INF = 1e9;
int myg[N][N];
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)
                myg[i][j] = min(myg[i][j], myg[i][k] + myg[k][j]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == j)
                myg[i][j] = 0;
            else
                myg[i][j] = INF;
        }
    for(int i = 1; i <= m; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        myg[x][y] = min(myg[x][y], z);
    }
    floyd();
    while(k--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(myg[x][y] > INF / 2)
            puts("impossible");
        else
            printf("%d\n", myg[x][y]);
    }
    return 0;
}