RodneyX

弗洛伊德算法是用于求解無(wú)負(fù)權(quán)回路的圖的任意一對(duì)頂點(diǎn)間最短路徑的算法，該算法采用的基本思想是動(dòng)態(tài)規(guī)劃（轉(zhuǎn)移方程就是cost[i][j] = cost[i][k] + cost[k][j] < cost[i][j] ? cost[i][k] + cost[k][j] : cost[i][j]）

算法步驟：令初始鄰接矩陣matrix[][]為cost[][]，對(duì)于每個(gè)頂點(diǎn)k，檢查以此為中轉(zhuǎn)頂點(diǎn)，對(duì)每對(duì)頂點(diǎn)i和j，若cost[i][k] + cost[k][j] < cost[i][j]則更新cost[i][j] = cost[i][k] + cost[k][j]，并且同時(shí)記錄下這個(gè)中轉(zhuǎn)的頂點(diǎn)k于path[i][j]中，檢查完每個(gè)頂點(diǎn)即可

代碼如下

// 復(fù)用數(shù)據(jù)結(jié)構(gòu)鄰接矩陣，見(jiàn) http://www.rzrgm.cn/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);
}

關(guān)于路徑任意一對(duì)頂點(diǎn)u和v間的最短路徑的查找方式是先找到path[u][v]，其中path[u][v]指明了u和v的最短路徑的中間頂點(diǎn)，即path[u][v] = k，則有路徑u -> ... -> k ... -> v，這樣遞歸地查找<u, k>和<k , v>的中間頂點(diǎn)即可，規(guī)定path[i][j] = -1時(shí)無(wú)中間頂點(diǎn)，即路徑是i -> j

這個(gè)算法的時(shí)空復(fù)雜度都很顯然，不必多說(shuō)