Floyd算法

用来求所有顶点间的最短路径，任意两点之间

let dist = [
    [0, 1, Infinity, 3],
    [Infinity, 0, 7, 5],
    [Infinity, Infinity, 0, Infinity],
    [Infinity, Infinity, 3, 0]
];
function Floyd(n) {
    for (let k = 0; k < n; ++k)
        for (let i = 0; i < n; ++i)
            for (let j = 0; j < n; ++j)
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
Floyd(4);
console.log(dist);
/*输出结果:
[
  [ 0, 1, 6, 3 ],
  [ Infinity, 0, 7, 5 ],
  [ Infinity, Infinity, 0, Infinity ],
  [ Infinity, Infinity, 3, 0 ]
]
*/

Bellman-Ford算法

Dijkstra算法

单源最短路径，一顶点到其余顶点

let matrix = [
    [0, 1, Infinity, 3],
    [Infinity, 0, 7, 5],
    [Infinity, Infinity, 0, Infinity],
    [Infinity, Infinity, 3, 0]
];

function Dijkstra(matrix, start = 0) {
    // rows和cols一样，其实就是顶点个数
    const rows = matrix.length, cols = matrix[0].length;
    if (rows !== cols || start >= rows)
        return new Error("邻接矩阵错误或者源点错误");
    // 初始化distance
    let distance = new Array(rows).fill(Infinity);
    // 初始化访问节点
    let visited = new Array(rows).fill(false);
    distance[start] = 0;
    for (let i = 0; i < rows; i++) {
        // 更新节点访问
        visited[start] = true;
        // 达到不了的顶点不能作为中转跳点
        if (distance[start] < Infinity) {
            for (let j = 0; j < cols; j++) {
                // 通过比较distance[start] + matrix[start][j]和distance[j]的大小来决定是否更新distance[j]。
                if (matrix[start][j] + distance[start] < distance[j]) {
                    distance[j] = matrix[start][j] + distance[start];
                }
            }
        }
        // 找到当前最短路径顶点作为中转跳点
        let minIndex = -1;
        let min = Infinity;
        for (let k = 0; k < rows; k++) {
            if (!visited[k] && distance[k] < min) {
                min = distance[k];
                minIndex = k;
            }
        }
        start = minIndex
    }
    return distance;
}

let res = Dijkstra(matrix, 0);
console.log(res);