「数据结构」Floyd算法

「Data Structre」Floyd

Posted by PYQ on May 16, 2022

Ⅰ. 推荐课程

【浙江大学】数据结构,浙大的数据结构讲的很精炼,不枯燥易懂,十分适合数据结构的学习。

以下笔记也是根据以该课程为主,并加以具体实现代码。

Ⅱ. Floyd算法

Dijkstra算法可以求解单个点到其他点的最短路径,若要求任意两点之间的最短距离,使用Dijkstra算法则显得有些麻烦。为了解决这个问题,我们可以使用Floyd算法

Floyd算法:Floyd算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。其时间复杂度为$O(N^3)$(因为代码里面有三个for循环),空间复杂度为$O(N^2)$。

Floyd算法采用了动态规划的思想,当求任意两点i,j的最短路径时有两种可能:

  • i直接到j,即Dis(i, j)
  • i经过某个点v到j,即Dis(i,v) + Dis(v,j)

通过将上述两种情况相比较,从而确定i,j两点之间的最短路径。假设图G一共有N个顶点,分别用这N个顶点作为中介点进行路径更新,更新N此后即可求得任意两点之间的最短路径。

Ⅲ. 代码

在编写代码的时候,我们需要两个N*N的数组dist和path,分别表示i,j两点之间的最短距离,以及i,j两点最短距离所经过的顶点。

关于三个for循环顺序为k,i,j的解释

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
// 邻接矩阵
typedef struct _graph{
    char vexs[MAX];       // 顶点集合
    int vexnum;           // 顶点数
    int edgnum;           // 边数
    int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;

/*
 * floyd最短路径。
 * 即,统计图中各个顶点间的最短路径。
 *
 * 参数说明:
 *        G -- 图
 *     path -- 路径。path[i][j]=k表示,"顶点i"到"顶点j"的最短路径会经过顶点k。
 *     dist -- 长度数组。即,dist[i][j]=sum表示,"顶点i"到"顶点j"的最短路径的长度是sum。
 */
void floyd(Graph G, int path[][MAX], int dist[][MAX]){
    // 初始化
    for (int i = 0; i < G.vexnum; i++){
        for (int j = 0; j < G.vexnum; j++){
            dist[i][j] = G.matrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
            path[i][j] = -;                 // "顶点i"到"顶点j"的最短路径是经过顶点j。
        }
    }

    // 计算最短路径,k表示中介点
    for (int k = 0; k < G.vexnum; k++){
        for (int i = 0; i < G.vexnum; i++){
            for (int j = 0; j < G.vexnum; j++){
                // 如果经过下标为k顶点路径比原两点间路径更短,则更新dist[i][j]和path[i][j]
               int tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                if (dist[i][j] > tmp){
                    // "i到j最短路径"对应的值设,为更小的一个(即经过k)
                    dist[i][j] = tmp;
                    // "i到j最短路径"对应的路径,经过k
                    path[i][j] = k;
                }
            }
        }
    }

    // 打印floyd最短路径的结果
    printf("floyd: \n");
    for (int i = 0; i < G.vexnum; i++){
        for (int j = 0; j < G.vexnum; j++)
            printf("%2d  ", dist[i][j]);
        printf("\n");
    }
}