Dijkstra算法——求某一个点到其他所有点的最短路径

Dijkstra算法和最小生成树的Prim算法又有异曲同工之妙。都是要将顶点分成两坨，一坨未访问的，一坨已访问的，通过循环将未访问的一次次拉下水，变成访问过的，在这个过程中，每次都找权值最小的路径。

以A点为例：

初始化A点到所有其他点的距离dis = [0, ∞, ∞]（依次代表[【AA】【AB】【AC】]）;
设当前点为A，当前路径dis[0] = 0；
已访问点集为{A}，未访问点集为{B,C}；
从未访问点集{B,C}中找到所有由当前点A和一个未访问集中的点组成的边【AC，10】【AB，8】，
遍历所有找到的边，通过（当前路径权重+找到的边的权重）和（找的边在dis中对应的权重）的比较，取更小的权重。这里∞ > 0 + 8, ∞ > 0 + 10,更新dis = [0, 8, 10];
找出dis中的包含未访问点集中某点的最小权边；此时有三条边【AA,0】【AB,8】【AC,10】，最小权是【AA，0】但是不没有包含未访问点集中的点所以不算，这里是【AB，8】；
这时A通过边【AB】拉下水了一个新的顶点B（为什么第6歩要包含未访问点集中的点）；
设当前点为B，当前路径为dis[1] = 8；
更新已访问点集为{A,B}，未访问点集为{C}；
从未访问点集{C}中找到所有由当前点B和一个未访问集中的点组成的边【BC，1】；
遍历所有找到的边，通过（当前路径权重+找到的边的权重）和（找的边在dis中对应的权重）的比较，取更小的权重，这里10 > 8 + 1 更新dis = [0, 8, 9];
找出dis中的包含未访问点集中某点的最小权边；此时有三条边【AA,0】【AB,8】【AC,9】，【AA，0】【AB，8】没有包含未访问点集中的点所以不算，这里是【AC，9】；
这时A通过边【AC】（实际上是【AB】+【BC】）拉下水了一个新的顶点C；
设当前点为C，当前路径为dis[2] = 9；
更新已访问点集为{A,B,C}，未访问点集为{}；
未访问点集为空，结束。

好了，开始程序设计

还是这张图（图片来源链接）

建立图表示

// 无向图
let vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
let edges = [
    [0, 1, 12],
    [0, 5, 16],
    [0, 6, 14],
    [1, 2, 10],
    [1, 5, 7],
    [2, 3, 3],
    [2, 4, 5],
    [2, 5, 6],
    [3, 4, 4],
    [4, 5, 2],
    [4, 6, 8],
    [5, 6, 9]
];

一个方法，用于找到所有（由当前点和未访问集中一点组成的边）

/**
 * @description 找到当前点在未访问点集合中的所有边
 * @param {vertex} src 源顶点
 * @param {Array<vertex>} objs 目标顶点数组
 * @param {Array<edge>} edges 所有边
 * @param {Array<vertex>} vertices 所有顶点
 * @returns {Array} edges
 */
function findEdgesIn(src, objs, edges, vertices) {
    let edgesBetweenSrcObj = [];
    for (const edge of edges) {
        srcIndex = vertices.indexOf(src);
        for (const obj of objs) {
            objIndex = vertices.indexOf(obj);
            if (edge[0] === srcIndex && edge[1] === objIndex || edge[0] === objIndex && edge[1] === srcIndex) { // 无向
            // if (edge[0] === srcIndex && edge[1] === objIndex) { // 有向
                edgesBetweenSrcObj.push(edge);
            }
        }
    }
    return edgesBetweenSrcObj;
}

男主角（dijkstra）

function dijkstra(vertices, edges, startVertex) {
    let infected = []; // 已访问点集
    let remained = vertices.slice(0); // 未访问的点集
    let shortestPath = vertices.slice(0).map(d => Infinity); // 路径数组
    shortestPath[vertices.indexOf(startVertex)] = 0; // 到自己路径为0
    let cur = startVertex; // 起始顶点
    while (remained.length !== 0) {
        infected.push(cur); // 标记当前点已访问(即顶点访问顺序)
        let curIndex = vertices.indexOf(cur); // 当前点索引
        remained.splice(remained.indexOf(cur), 1); // 从未访问中删除当前点
        let foundEdges = findEdgesIn(cur, remained, edges, vertices); // 找到所有含有当前点的边
        for (const e of foundEdges) {
            let eIndex = curIndex === e[0] ? e[1] : e[0]; // 顶点索引，无向
            // let eIndex = e[1]; // 顶点索引，有向
            if(shortestPath[eIndex] > shortestPath[curIndex] + e[2]){
                shortestPath[eIndex] = shortestPath[curIndex] + e[2]; // 更新路径
            }
        }
        let newIndex = null; // 最小边新入顶点索引
        for(let i = 0; i < shortestPath.length; i ++){
            if(remained.indexOf(vertices[i]) !== -1){
                // 从未被访问的点中找一个最短路径，返回其顶点索引
                newIndex = newIndex ? (shortestPath[newIndex] < shortestPath[i] ? newIndex : i) : i;
            }
        }
        cur = vertices[newIndex]; // 更新当前顶点
    }
    return {
        path: infected,
        distance: shortestPath
    }
}

// 打印结果
{ path: [ 'A', 'B', 'G', 'F', 'C', 'D', 'E' ],
  distance: [ 0, 12, 22, 25, 27, 16, 14 ] }

Floyd算法——求各个顶点两两之间的最短路径

感谢该文章作者的讲解，本文借用其所讲的例子，故列出原文链接，尊重版权（顺带一提，博客左下角有惊喜）。
参考文章：https://www.cnblogs.com/ECJTUACM-873284962/p/6995648.html

简单粗暴的核心：3个for循环

其实核心思想是：将每条路径拆分成其他两条路径的组合，如果两条路径组合的权重更小就替代之。

细节的我不码字了，上代码以供参考。老板，上图！

表示图形

// 矩阵存储
let graphMatrix = [
    [0, 2, 6, 4],
    [Infinity, 0, 3, Infinity],
    [7, Infinity, 0, 1],
    [5, Infinity, 12, 0]
];

Floyd算法

// 最短路径弗洛伊德算法
function floyd(graphMatrix) {
    let matrixCopy = graphMatrix.slice(0);
    for (let i = 0; i < graphMatrix.length; i++) {
        // Ai矩阵
        for (let j = 0; j < graphMatrix.length; j++) {
            for (let k = 0; k < graphMatrix.length; k++) {
                matrixCopy[j][k] = Math.min(matrixCopy[j][k], matrixCopy[j][i] + matrixCopy[i][k]);
            }
        }
    }
    console.log(matrixCopy)
    return matrixCopy;
}

// 打印结果
[ [ 0, 2, 5, 4 ],
  [ 9, 0, 3, 4 ],
  [ 6, 8, 0, 1 ],
  [ 5, 7, 10, 0 ] ]

数据结构のJavaScript实现之最短路径（Dijkstra算法和Floyd算法）

Dijkstra算法——求某一个点到其他所有点的最短路径

Floyd算法——求各个顶点两两之间的最短路径