Floyd多源最短路

可以对每一个顶点使用Dijkstra算法求多源最短路。

这里我们来介绍另一种解法：Floyd

Floyd算法的主要思想是迭代。每次迭代会朝着答案更近一步。

首先定义一个二维数组D^k[i][j](k初始等于0).这个二维数组代表从i到j的最短距离。

Floyd更适合解决稠密图，所以我们使用邻接矩阵来表示图。

初始化：

如果i，j有路 D⁰[i][j] = G[i][j] （G为我们的邻接矩阵）

否则 D⁰[i][j] = INF（正无穷大）

（1）我们加入一个顶点，这个点的加入可能会影响到某两个点之间的最短路。所以检查任意i到k， k到j之间的距离。

　　　　如果 D^k-1[i][k] + D^k-1[k][j] < D^k[i][j]

　　　　　　　　更新：D^k[i][j] = D^k-1[i][k] + D^k-1[k][j]

（2）循环加入每一个顶点，直到所以顶点都被加入，Floyd结束。

（如果我们想得到两个点之间的路径，在执行算法的同时记录path[i][j])

#define MaxVertexNum 100000

typedef int Vertex;

typedef struct Node

{

    Vertex id;

}Node;

typedef struct MyGraph

{

    int g[MaxVertexNum][MaxVertexNum];

    int v, e;

}MyGraph;

void Floyd(MyGraph& G, int D[][], Vertex path[][])

{

    //初始化

    for(Vertex i = ; i < G.v; i++)

    {

        for(Vertex j = ; j < G.v; j++)

        {

            if(G.g[i][j] == -)

                D[i][j] = INF;

            else

                D[i][j] = G.g[i][j];

        }

    }

    //迭代

    for(Vertex k = ; k < G.v; k++)

    {

        for(Vertex i = ; i < G.v; i++)

        {

            for(Vertex j = ; j < G.v; j++)

            {

                //如果得到更小的路径，更新

                if(D[i][j] > D[i][k] + D[k][j])

                {

                    D[i][j] = D[i][k] + D[k][j];

                    path[i][j] = k;

                }

            }

        }

    } 

}

巴特西

Floyd多源最短路

最新文章

热门文章