JS实现最短路径之迪杰斯特拉(Dijkstra)算法

JS实现最短路径之迪杰斯特拉(Dijkstra)算法

迪杰斯特拉(Dijkstra)算法是典型法是典型的单源最短路径算法，用于计算一个节点到其他节点的最短路径。 
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

迪杰斯特拉 ( Dijkstra) 算法是 一个按路径长度递增的次序产生最短路径的算法。时间复杂度为 O(n2)，n为顶点个数，如果是从其他顶点开始，那么在原有算法的基础上再来一次循环，此时的时间复杂度为O(n3)。

如下图v0为源点，v8为终点，如果找出最优最短的路径呢？

迪杰斯特拉 ( Dijkstra) 算法是并不是一下子就求出 了 Vo 到V8 的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果

整个的过程如下图：

具体的实现代码如下：

    <script type="text/javascript">
        //定义邻接矩阵
        let Arr2 = [
            [0, 1, 5, 65535, 65535, 65535, 65535, 65535, 65535],
            [1, 0, 3, 7, 5, 65535, 65535, 65535, 65535],
            [5, 3, 0, 65535, 1, 7, 65535, 65535, 65535],
            [65535, 7, 65535, 0, 2, 65535, 3, 65535, 65535],
            [65535, 5, 1, 2, 0, 3, 6, 9, 65535],
            [65535, 65535, 7, 65535, 3, 0, 65535, 5, 65535],
            [65535, 65535, 65535, 3, 6, 65535, 0, 2, 7],
            [65535, 65535, 65535, 65535, 9, 5, 2, 0, 4],
            [65535, 65535, 65535, 65535, 65535, 65535, 7, 4, 0],
        ]

        let numVertexes = 9, //定义顶点数
        numEdges = 15; //定义边数

        // 定义图结构
        function MGraph() {
            this.vexs = []; //顶点表
            this.arc = []; // 邻接矩阵，可看作边表
            this.numVertexes = null; //图中当前的顶点数
            this.numEdges = null; //图中当前的边数
        }
        let G = new MGraph(); //创建...

点击查看剩余70%