JavaScript与Dijkstra 最短路算法

分手后的思念是犯贱 2022-05-26 02:47 182阅读 0赞

## 背景 ##

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

Floyd 最短路算法用于求解任意两点的最短路径，称为“多源最短路”。下面我们介绍指定一个点到其他各个顶点的最短路径，叫做：单源最短路径。  
下面我们还是先给出本篇文章讲解依赖的图：  
![这里写图片描述][70]

## 数据结构 ##

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

同样，我们使用一个二维数组存储上述图的信息。

## 求解过程 ##

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

根据上图：我们可以得到初始矩阵**path**：  
![这里写图片描述][70 1]

前面我们说过dijkstra是“单源最短路径”，在讲解求解过程之前，我们就选择0号顶点作为源点。

选择好了源点，我们还需要一个一维数组用来存储源点到各个顶点的距离，  
如下为初始值：

![这里写图片描述][70 2]

此时我们称dis数组为最短路的“估计值”。

下面我们根据上述信息，一步步的去更新**dis**数组，得到最后的结果。

#### 计算过程 ####

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

既然是求0号顶点到其他顶点的最短距离，那我们首先根据**dis**数组，找出当前距离0号顶点最近的一个顶点，我们可以找到1号顶点距离0号顶点最近。此时，我们就可以确定0号顶点到1号顶点最短距离。也就是说**dis\[1\]**从估计值变成了确定值。这个时候你可能会想为什么？我们可以这样思考，找最短路径的途径就是看能不能找到中转点从而减少距离，由于我们取得是**dis**中的最小值，那么不可能再找到中转点从而减少**0**到**1**的距离。

既然我们已经确认了0号到1号的最短距离，这个时候我们就去更新我们的**dis**数组，如何更新呢？我们可以把**1**号顶点作为中转点，通过查看初始矩阵**path**，通过比较**dis\[1\] + path\[1\]\[i\]**和**dis\[i\]**的大小来决定是否更新**dis\[i\]**。更新结束之后，我们得到：  
![这里写图片描述][70 3]

更新完**dis**之后，依据更新的**dis**，从未确定距离的点中选出距离最短的那个，这个距离就变成了确定值，紧接着去更新**dis**数组。得到：  
![这里写图片描述][70 4]

紧接着重复执行上述动作，依次得到更新的**dis**数组为：  
![这里写图片描述][70 5]  
![这里写图片描述][70 6]

最后一张图，就是最后的结果。

#### 总结 ####

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

根据上述流程，我们做出如下总结：

*  将所有的顶点分为两个部分：已知最短距离的顶点集合**P**和未知最短距离的顶点集合**Q**。最开始的时候，已知最短距离的顶点集合中只有源点。
 *  初始化**dis**数组，将源点**s**到自己的距离设置为0。如果存在源点能够直接到达的顶点**i**，那么将**dis\[i\]**设置为**path\[s\]\[i\]**，否则设置为**Infinity**。
 *  依据**dis**数组，在未知顶点集合**Q**中选出距离源点最近的一个顶点**u**，放入**P**中，并考察所有以**u**为起点的边，以**u**作为中转点，检验是否能够减短源点到其他点的距离。如果有，就更新**dis**数组。
 *  重复上一步骤，直到**Q**中没有顶点。
    
    ## 完整代码 ##

//求解index号顶点到达其他顶点的最短距离
    function dijkstra(path,index){ 
        var m = path && path.length;
        var n = m && path[0].length;
    
        if(m && n && m===n && index < n){
            //初始化distance
            var dis = [];
            var i;
            for(i = 0; i< n;i++){
                dis.push(path[index][i]);
            }
            var flag = [];//用于标识index号至其他顶点的距离是否确定
            for(i = 0; i < n; i++ ){
                flag.push(false)
            }
            flag[index] = true;
    
            var min,minIndex;
            for(i = 0;i < n;i++){
                min = Infinity;
                //找出剩余的不确定的点到index最短的距离对应的索引
                for(var j = 0; j < n; j++){
                    if(!flag[j] && dis[j] < min){
                        min = dis[j];
                        minIndex = j;
                    }
                }
                flag[minIndex] = true;//标识index到此顶点的距离已经确认
                for(var k = 0; k < n; k++){
                    //判断minIndex到k之间有无道路
                    if(path[minIndex][k] < Infinity){
                        //更新distance
                        if(dis[k] > dis[minIndex] + path[minIndex][k]){
                            dis[k] = dis[minIndex] + path[minIndex][k];
                        }
                    }
                }
            }
            return dis;
        }
        else{
            throw new Error("数据有误")
        }
    }

[70]: /images/20220526/1cab07d78a2c4a1bb68c77f9b8782cd3.png
[70 1]: /images/20220526/694682a91ac240499ad6c71697a2ee11.png
[70 2]: /images/20220526/0d1384130d084a5088d70dc58a638b4a.png
[70 3]: /images/20220526/93ffe57305b641ad8c9d6e6ad794c3d0.png
[70 4]: /images/20220526/1540be6279ad45a699a087f5ca0d5f9c.png
[70 5]: /images/20220526/47a5c0a9c2a14678acbd4aa2faa15bff.png
[70 6]: /images/20220526/4a308eddb3b0429eaaf411ef33f9981b.png