JavaScript与Floyd 最短路算法

朱雀 2022-05-29 06:06 183阅读 0赞

## 背景 ##

--------------------

NBA超级后场组合**灯泡组合**(Harden和CP3)休赛期来到中国玩耍，他们两人打算在四个城市进行玩耍，最后他们选择了北京、上海、西安和长沙。假设这四个城市之间有些城市之前有航线，而有些城市之间没有航线。为了方便行程，出发前，他们想要知道任意两个城市之间的最短路程。如果下图就是航线图：

![这里写图片描述][SouthEast]

## 数据结构 ##

--------------------

我们使用一个二维数组**Path**来存储上述图的信息。比如说1号城市到二号城市之间的距离可以存储为**Path\[0\]\[1\] = 2**，而2号城市无法直接到达1号城市我们记**Path\[1\]\[0\] = Infinity**。另外我们约定一个城市到达本身的距离为0，即**Path\[0\]\[0\] = 0**。

## 思路 ##

--------------------

想要使两个城市（**x**，**y**）之间的距离变短，此时我们可以引入第三个城市作为中转点（**z**），本来是**x->y**，现在变成**x->z->y**，只有这样才有可能缩短**x**和**y**之间的距离，那么这个中转点**z**到底是哪个城市，或者可以说这个**z**代表的是多个中转点，因为有时候经过多个中转点，**x**和**\*y**之间的距离会更短。下面我们通过一步步的添加中转点，来更新两点之间的最短距离。

## 过程 ##

--------------------

我们依照最上面的航线图，解释如何得到最短路径。  
当任意两个城市之间不允许经过第三个城市的时候，得到的矩阵如下：

![这里写图片描述][SouthEast 1]

第一步：  
现在我们只允许经过1号城市这个中转点，这个时候如何求解任意两点之间的最短距离。我们只需进行如下比较：

Path[i][0] + Path[0][j] < Path[i][j]

其中**Path\[i\]\[j\]**表示的是城市**i+1**和**j+1**（因为JS中，数组索引从0开始）之间的距离。而**Path\[i\]\[0\] + Path\[0\]\[j\]** 表示的是先从**i+1**到**1**号城市，再从**1**到**j+1**的距离之和。  
这个时候把**i**从**0~n-1**循环，把**j**从**0~n-1**循环，既可以得到当经过中转点1号城市的时候，任意两点之间的最短距离。

代码实现：

for(var i = 0; i < n; i++ ){
        for(var j = 0; j < n; j++){
            if(Path[i][0] + Path[0][j] < Path[i][j]){
                Path[i][j] = Path[i][0] + Path[0][j];
            }
        }
    }

这个时候我们可以把最短距离矩阵更新为：  
![这里写图片描述][SouthEast 2]

从上图可以看出，在经过中转点：1号城市的时候，有几个城市之间的最短距离减少了。

接下来，我们要做的就是增加中转点：2号城市。要执行的代码如下：

for(var i = 0; i < n; i++ ){
        for(var j = 0; j < n; j++){
            if(Path[i][0] + Path[0][j] < Path[i][j]){
                Path[i][j] = Path[i][0] + Path[0][j];
            }
        }
    }
    for(var i = 0; i < n; i++ ){
        for(var j = 0; j < n; j++){
            if(Path[i][1] + Path[1][j] < Path[i][j]){
                Path[i][j] = Path[i][1] + Path[1][j];
            }
        }
    }

我们可以继续更新距离矩阵为：  
![这里写图片描述][SouthEast 3]

从上图可以看出，增加中转点后，有些城市之间的最短距离进一步减小。

同理，我们进一步增加中转点城市3和城市4，就可以得到最终的距离矩阵为：  
![这里写图片描述][SouthEast 4]

下面给出一个完整函数：

//接收一个参数，参数即用二维数组存储的距离矩阵
    function floyd(Path){ 
        var n = Path && Path.length;
        var m = n && Path[0].length;
        if(m && n && m===n){
            for(var k = 0; k < n; k++){
                for(var i = 0; i < n; i++ ){
                    for(var j = 0; j < n; j++){
                        if(Path[i][k] + Path[k][j] < Path[i][j]){
                            Path[i][j] = Path[i][k] + Path[k][j];
                        }
                    }
                }
            }
        }
    }

> 注意：Floyd算法不能解决带有“负权回路”（或者叫“负权环”）的图。因为带有“负权回路”的图没有最短路。

[SouthEast]: /images/20220529/4129afbdb1d6484dbc97215164b5bc48.png
[SouthEast 1]: /images/20220529/7e440eb792fe42f5aa7c911fe3c792da.png
[SouthEast 2]: /images/20220529/73601cd077154bf294a1c1b83e7461de.png
[SouthEast 3]: /images/20220529/de3c7d31efcf475d83c53f18f0cb03b3.png
[SouthEast 4]: /images/20220529/f7695f2e10bb4e3a8effd3d4089a0ead.png