数据结构与算法学习笔记（5）——最短寻路

发表于   |   分类于   |  

接着上一章的内容，让我们来深入探讨最短路径的问题。

本文仅供个人记录和复习，不用于其他用途

最简短算法——Floyd Warshall

假如小明想要去一些城市旅游，这些城市之间有的有路，有的没有。如果他想知道任意两个城市之间的最短路径，那么应该怎么办呢？

我们先用二维数组将路径存储起来，然后呢，可以使用深度或广度来求出两点之间的最短路径。那么这样一来，我们只要进行n²遍搜索就能达到目的。那么，有没有更简单的方法呢？

我们知道，如果要让两点之间的距离变短，那么势必要引入第三个点。通过这个点的周转，两点之间的距离才有可能缩短。但是，通过一个点周转就一定是最短吗？我们可不可以引入第四个、第五个点来让路径更短呢？

由此，我们可以想到。对于两点之间的最短路径，我们只需要依次加入其他的点，判断借助这个点的周转后，是否要比原始的路径短。

1
2
3
4
5
// 借助1号顶点
for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
        if(e[i][j] > e[i][1] + e[1][j])
            e[i][j] = e[i][1] + e[1][j];

e[i][j]表示当前i到j的最短路径，e[i][1] + e[1][j]就表示i-1-j的路径。比较这两个值，如果后者小，那么将i到j的最短路径值更新。当然，我们这里直接借助了1号顶点，其他的顶点也会类似，因此我们只需要使用三层循环即可。

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
#include <stdio.h>
int main()
{
    int map[10][10], k, i, j, n, m, a, b, c;
    int wuxian = 99999999;
    printf("输入城市数和路径数：");
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            if(i == j)
                map[i][j] = 0;
            else
                map[i][j] = wuxian;
        }
    printf("输入数据：\n");
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        map[a][b] = c;
    }
    for(k = 1; k <= n; k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(map[i][j] > map[i][k] + map[k][j])  // map[i][j]表示的是i和j之间的最短路径，初始化之后，如果借助k城市能够更快的到达，那就将最短路径变为借助k城市的
                    map[i][j] = map[i][k] + map[k][j];  // 下一次k循环时，又会变成从i到k到k+1到j是否更短
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            printf("%10d", map[i][j]);
        }
        printf("\n");
    }
}

单源最短路径——Dijkstra

除了任意两点之间的路径，我们还需要了解一个点到其他各个顶点的最短路径。

假设我们要知道1号顶点到其他顶点的距离，那么这里设置一个一维数组dis来存储数据。dis数组首先初始化，也就是1号顶点直接到其他顶点的距离，无法到达用无限大来代替。不过要注意的是，这里的dis还并不是确定的值，我们需要判断dis数组中的数据是不是最短路径，如果不是则需要更新。

既然是求1号顶点到各个顶点的最短距离，那么就先找离1号顶点最近的点。1号顶点到2号顶点的距离为1，是1号到其他点中距离最小的，所以dis[2]就为1，成为了确定值。接着，我们看看2号顶点有哪些连接的边。可以看到，2号顶点连接着3号和4号。那么，通过2号顶点到达这两个点，会不会缩短路程呢？

显然，dis[3]=12，而dis[2]+e[2][3]=10，所以dis[3]要被更新为10。同理，dis[4]改为4。接下来，从3、4、5、6中选出一个离1号点最近的，重复这个过程，直到dis数组中所有数据成为确定值。

这个算法的思路在于，找出离单源最近的点。由于所有边的权值都为正数，所以单源到这个点的距离就是最短的，不可能再通过其他的点来缩短路程。随后，尝试通过这个点，来缩短到其他点的路程（这个过程被称为“松弛”）。接下来，便是找出除了这个点外离单源最近的点，然后重复上述过程，直到最后一个点。可以这么归纳：

  • 找出最近的点
  • 松弛
  • 找出剩下点中最近的
  • 松弛
  • ……
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
60
61
#include <stdio.h>
int main()
{
    int map[10][10], dis[10], book[10], i, j, n, m, t1, t2, t3, u, v, min;
    int wuxian = 99999999;
    printf("读入顶点和边：");
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            if(i == j)
                map[i][j] = 0;
            else
                map[i][j] = wuxian;
        }
    printf("读入边距：\n");
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &t1, &t2, &t3);
        map[t1][t2] = t3;
    }
    // 将1到各顶点的距离读入dis
    for(i = 1; i <= n; i++)
        dis[i] = map[1][i];
    // 初始化book数组，0表示还没处理的点，1表示已经处理
    for(i = 1; i <= n; i++)
        book[i] = 0;
    book[1] = 1;
    for(i = 1; i <= n - 1; i++)  // 最后一个点没有出边，无需处理
    {
        min = wuxian;  // 寻找距离1最近的点
        for(j = 1; j <= n; j++)
        {
            if(book[j] == 0 && dis[j] < min)  // 必须是没有处理过且最小
            {
                min = dis[j];
                u = j;
            }
        }
        book[u] = 1;  // 开始处理距离最短的点
        for(v = 1; v <= n; v++)
        {
            if(map[u][v] < wuxian)  // 开始循环遍历，如果u可以到v，那么判断从1到u到v和直接到v哪个快，对于地市进行更新
            {
                if(dis[v] > dis[u] + map[u][v])
                    dis[v] = dis[u] + map[u][v];
            }
        }
    }
    for(i = 1; i <= n; i++)
        printf("1到%d点的最短距离为%d\n", i, dis[i]);
}

解决负权边——Bellman Ford

假如有一个1-2-3-1的循环路线，如果存在负权边，那么之前提到的算法就会陷入死循环，因为只要走一次就能够减少路径。为了解决负权边问题，我们得学习学习新的算法。

1
2
3
4
for(k = 1; k <= n - 1; k++)
    for(i = 1; i <= m; i++)
        if(dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i];

外循环表示对n-1个顶点进行了遍历，内循环表示对m条边进行了遍历，dis数组同样是存储单源到各个顶点的最短距离。至于u、v、w表示，第i条边是从顶点u[i]到顶点v[i]，并且权值为w[i]。

很明显，从1号顶点开始，对n-1个顶点进行了松弛操作。当循环结束后，所有顶点相关的边都被松弛完毕，也就是说dis数组中存储的就是单源到各个顶点的最短路径。

至于为什么是n-1而不是n，那是因为n个顶点的途中，两点间最短路径最多包含n-1条边，不可能会出现回路。事实上，正权回路是多此一举，因为去掉之后路径更短。而负权回路中不可能存在最短路径，因为循环一次路径会缩短。

因为我们只循环n-1次，所以之前被松弛过的顶点，不会再受到之后顶点的影响，所以也不会出现负权边无限循环的情况。

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
// 事实上，该算法每次都只会松弛与当前顶点相连的边，循环了n-1个顶点后自然就松弛了所有的边，但是也存在许多不必要的运算，可以优化
#include <stdio.h>
int main()
{
    int dis[10], i, k, n, m, u[10], v[10], w[10];
    int inf = 99999999;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; i++)
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
    for(i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    for(k = 1; k <= n - 1; k++)  // 针对顶点进行边的松弛
        for(i = 1; i <= m; i++)
            if(dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];
    int flag = 0;
    for(i = 1; i <= m; i++)  // 如果还有边可以松弛，证明存在负权回路，无最短路径
        if(dis[v[i]] > dis[u[i]] + w[i])
            flag = 1;
    if(flag == 1)
        printf("存在负权回路");
    else
        for(i = 1; i <= n; i++)
            printf("%d ", dis[i]);
}

队列优化——Bellman Ford

其实这个算法还存在一点问题，那就是经历一次循环后，可能有些顶点的最短路的值已经确定，但我们还是要判断这个点需不需要松弛。因此，我们要改变一下策略，每次仅对最短路估计值发生了变化的顶点的所有出边进行松弛操作。

例如有一条边u-v，如果通过这条边使得从源点到v的路程变短，且顶点v不在队列中，那么就将顶点v放入队尾。我们这里只对队列中的点进行松弛操作，另外队列中不要出现重复的顶点。

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
60
61
62
// 队列优化解决了算法之中对于已达到最短路径后仍旧继续运算的问题，同时也只对还没有优化的顶点进行处理，而不是每一次循环都处理所有的边
#include <stdio.h>
int main()
{
    int n, m, i, j, k;  // n,m表示顶点数和边数，i,j,k用于计数
    // 本例使用邻接表来存储图，也就是模拟链表，至于为什么要大1，因为为了方便操作，数组下标从1开始使用
    // first用于记录每个顶点链接的第一条边，而next用于记录每条边链接的下一条边
    int u[8], v[8], w[8];  // u,v,w的数组大小根据实际情况，比m的值大1
    int first[6], next[8];  // first比n大1，next比m大1
    int dis[6] = {0}, book[6] = {0};
    int que[101] = {0}, head = 1, tail = 1;
    int inf = 99999999;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    for(i = 1; i <= n; i++)
        first[i] = -1;  // -1表示第i个顶点没有边
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);  // 记录第i条边
        next[i] = first[u[i]];  // next[i]存储第i条边的下一条边
        first[u[i]] = i;  // first[u[i]]存储顶点u[i]的第一条边的编号为i，也就是说first存储了每个顶点对应的第一条边
    }
    que[tail] = 1;  // 将1号顶点入队
    tail++;
    book[1] = 1;  // 标记1号顶点已在队中
    while(head < tail)  //队列不为空是才循环
    {
        k = first[que[head]];  // 当前需要处理的顶点，也就是队首对应的顶点，k接受当前顶点对应的第一条边
        while(k != -1)  // 如果当前顶点有边，那么便扫描顶点所有的边
        {
            if(dis[v[k]] > dis[u[k]] + w[k])  // 判断这条边能否松弛
            {
                dis[v[k]] = dis[u[k]] + w[k];  // 进行松弛
                if(book[v[k]] == 0)  // 如果0不在队列，那么将顶点v[k]入队
                {
                    que[tail] = v[k];
                    tail++;
                    book[v[k]] = 1;  // 标记v[k]已在队列
                }
            }
            k = next[k];  // 取出下一条边
        }
        book[que[head]] = 0;  // 队首顶点已经处理完毕，对应的边已经优化，无需再优化，出队
        head++;
    }
    int flag = 0;
    for(i = 1; i <= m; i++)  // 如果还有边可以松弛，证明存在负权回路，无最短路径
        if(dis[v[i]] > dis[u[i]] + w[i])
            flag = 1;
    for(i = 1; i <= n; i++)
        printf("%d ", dis[i]);
}

这里说一下邻接表。邻接矩阵我们已经了解过了，用于存储图，那么邻接表则是用链表的形式来存储边的信息。不过这里其实并没有使用指针链表，而是采用了数组的形式。

首先u、v、w上面已经提过，这里我们新建两个数组first和next来存储边的信息。first[u[i]]保存顶点u[i]的第一条边的编号，next[i]表示第i条边的下一条边的编号。听起来有点复杂，我们来看个例子：

  • 读入第一条边1 4 9，first[1] = 1，next[1] = -1
  • 读入第二条边4 3 8，first[4] = 2，next[2] = -1
  • 读入第三条边1 2 5，first[1] = 3，next[3] = 1
  • 读入第四条边2 4 5，first[2] = 4，next[4] = -1
  • 读入第五条边1 3 7，first[1] = 5，next[5] = 3

这个是怎么遍历的呢？我们通过first[1]找到第五条边，然后通过next[5]找到第三条边，最后通过next[3]找到第一条边：

1
2
3
4
5
6
7
8
9
for(i = 1; i <= n; i++)
{
    k = first[i];
    while(k != -1)
    {
        printf("%d %d %d\n", u[k], v[k], w[k]);
        k = next[k];
    }
}

我们会发现，存储next时，顺序是反的，所以我们在遍历每个顶点的边时，应该和读入的顺序相反。事实上，顶点插入边的时候都是直接插入链表的首部而不是尾部，不过正因为是相反的，才会达到我们想要的效果。