浅谈Floyd算法

13天前发布

弗洛伊德算法是用于求解无负权回路的图的任意一对顶点间最短路径的算法，该算法采用的基本思想是动态规划（转移方程就是cost[i][j] = cost[i][k] + cost[k][j] < cost[i][j] ? cost[i][k] + cost[k][j] : cost[i][j]）

算法步骤：令初始邻接矩阵matrix[][]为cost[][]，对于每个顶点k，检查以此为中转顶点，对每对顶点i和j，若cost[i][k] + cost[k][j] < cost[i][j]则更新cost[i][j] = cost[i][k] + cost[k][j]，并且同时记录下这个中转的顶点k于path[i][j]中，检查完每个顶点即可

代码如下

// 复用数据结构邻接矩阵，见 https://www.cnblogs.com/RodneyTang/p/19010305
void floyd(adjMaxtrix &mGraph, int **&path, int **&cost)
{
    path = (int **)malloc(sizeof(int *) * mGraph.vnum);
    cost = (int **)malloc(sizeof(int *) * mGraph.vnum);
    for (int i = 0; i < mGraph.vnum; ++i)
        path[i] = (int *)malloc(sizeof(int) * mGraph.vnum);
    for (int i = 0; i < mGraph.vnum; ++i)
        for (int j = 0; j < mGraph.vnum; ++j)
        {
            path[i][j] = -1;
            cost[i][j] = mGraph.matrix[i][j];
        }

    for (int k = 0; k < mGraph.vnum; ++k)
        for (int i = 0; i < mGraph.vnum; ++i)
            for (int j = 0; j < mGraph.vnum; ++j)
                if (cost[i][k] <= INT_MAX / 2 && cost[k][j] <= INT_MAX / 2 && cost[i][j] > cost[i][k] + cost[k][j])
                {
                    cost[i][j] = cost[i][k] + cost[k][j];
                    path[i][j] = k;
                }
}

int *floyd_path(int **path, int **cost, int u, int v, int vnum)
{
    if (cost[u][v] == INT_MAX)
        return nullptr;
    int index = 1, *re_path = (int *)malloc(sizeof(int) * vnum), &r_index = index;
    for (int i = 0; i < vnum; ++i)
        re_path[i] = -1;
    _floyd_path(path, u, v, re_path, index);
    re_path[0] = u;
    re_path[index] = v;
    return re_path;
}

void _floyd_path(int **path, int u, int v, int *re_path, int &index)
{
    if (path[u][v] == -1)
        return;
    int k = path[u][v];
    _floyd_path(path, u, k, re_path, index);
    re_path[index++] = k;
    _floyd_path(path, k, v, re_path, index);
}

关于路径任意一对顶点u和v间的最短路径的查找方式是先找到path[u][v]，其中path[u][v]指明了u和v的最短路径的中间顶点，即path[u][v] = k，则有路径u -> ... -> k ... -> v，这样递归地查找<u, k>和<k , v>的中间顶点即可，规定path[i][j] = -1时无中间顶点，即路径是i -> j