【数据结构】最短路径算法之弗洛伊德算法

我不是女神ヾ 2022-10-02 12:51 201阅读 0赞

## 基本概念 ##

最简单的最短路径是求中转次数最少的路径，而不考虑每条边的权值。而在实际问题中，路径长度的度量就不再是路径上的边数，而是**路径上所有边的权值之和**。

在**有向网**中，习惯上称路径的第一个顶点为**源点（Source）**，最后一个顶点为**终点（Destination）**。

下面主要讨论**两种**最常见的最短路径问题：

一、从**某个源点**到其余顶点的最短路径；

二、求**每一对顶点**之间的最短路径。

**迪杰斯特拉(Dijkstra)算法**用于求解第一种问题，时间复杂度为**O(n²)**；**弗洛伊德(Floyd)算法**用于求解第二种问题，时间复杂度为**O(n³)**。

从实现形式上来说，弗洛伊德算法比迪杰斯特拉算法更为**简洁**。

## 弗洛伊德算法（顶点对） ##

求解每一对顶点之间的最短路径有两种方法：

一种是n次调用迪杰斯特拉算法；

另一种是采用下面介绍的弗洛伊德算法。

两种算法的时间复杂度均为O(n³)，但弗洛伊德算法的形式更为简洁。

**<逻辑思路>**

（1）如果说迪杰斯特拉算法是一个**“加边”**的过程，那么弗洛伊德算法就是一个**“加点”**的过程；

（2）先确定两个目标顶点，源点为vs，终点为ve；

（3）若vs和ve之间存在弧，初始化为**arcs\[vs-1\]\[ve-1\]**（编号），反之置为∞；

（4）依次判断剩余顶点vi，若在两个顶点间插入vi后，使得**<vs,vi>+<vi,ve>小于<vs,ve>**，则置换为vs和ve间的最短路径；

（5）直至所有剩余顶点判断完毕，最短路径确定；

（6）其余的每一对顶点都重复上述过程。

**<实现思路>——以邻接矩阵为存储结构的有向网**

（1）该算法的核心思想是设置了两个二维辅助数组：

1. 二维数组Path\[\]\[\]：行表示顶点vi的直接前驱，列表示顶点vi；

2. 二维数组D\[\]\]\[\]：记录vs和ve间的最短路径。

（2）弗洛伊德算法的代码思路比较清晰，插入、比较、更新。

void ShortestPath_Floyd(AMGraph G)
    {
    /*-----------初始化------------*/
        for(int vs = 1; vs <= G.vexnum; vs++)         /*源点vs*/
        {
            int i = LocateVex(G, vs);
    
            for(int ve = 1; ve <= G.vexnum; ve++)     /*终点ve*/
            {
                int j = LocateVex(G, ve);
    
                D[i][j] = G.arcs[i][j];
                
                if(D[i][j] < MaxInt && i != j)
                    Path[i][j] = i;
                else Path[i][j] = -1;
            }
               
    /*---------初始化结束--------*/
    
        for(int vi = 1; vi <= G.vexnum; vi++)         /*插入点vi*/
            for(int vs = 1; vs <= G.vexnum; vs++)     /*源点vs*/
                for(int ve = 1; ve <= G.vexnum; ve++) /*终点ve*/
                    {
                        int k = LocateVex(G, vi);
                        int i = LocateVex(G, vs);
                        int j = LocateVex(G, ve);
                
                        if(D[i][k] + D[k][j] < D[i][j])       /*更新*/
                        {
                            D[i][j] = D[i][k] + D[k][j];
                            
                            Path[i][j] = k;
                        }
                    }
    }