Floyd多源最短路

佚名 6年前 (2019-04-22) 随笔 1579人围观抢沙发百度已收录

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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 = 0; i < G.v; i++)
    {
        for(Vertex j = 0; j < G.v; j++)
        {
            if(G.g[i][j] == -1)
                D[i][j] = INF;
            else
                D[i][j] = G.g[i][j];
        }
    }
    
    //迭代
    for(Vertex k = 0; k < G.v; k++)
    {
        for(Vertex i = 0; i < G.v; i++)
        {
            for(Vertex j = 0; 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;
                }    
            }    
        }    
    } 
    
}