Dijkstra算法

JavaScript 代码

function Dijkstra(adj_matrix, src) {
    // dist 存储路径值(权)
    // visited 存储顶点是否访问
    let dist = []
    let visited = []

    const length = adj_matrix.length
    const INF = Number.MAX_SAFE_INTEGER

    // 初始化dist和visited列表
    for (let i = 0; i < length; i++) {
        dist[i] = INF
        visited[i] = false
    }

    // 选择第一个节点进入循环
    dist[src] = 0
    let i = 0
    while (i < length - 1 && src < length) {
        // 此时对应节点已经访问
        visited[src] = true
        // 找到对应节点的对应的边集合
        let currentEdges = adj_matrix[src]
        // 遍历边，更新路径
        for (let i = 0; i < currentEdges.length; i++) {
            if (currentEdges[i] !== 0) {
                // 存在边，找到最短路径，例如：
                // A=>B=>C 最短路径的权
                // 为 A=>B 的权(dist[src]) +  B=>C的权(currentEdegs[i]) 和 A=>C(dist[i]) 的权 进行比较
                if (dist[src] + currentEdges[i] < dist[i]) {
                    // 符合上面条件 更新dist[i] 保证dist[i]是每次探路的最短路径
                    dist[i] = currentEdges[i] + dist[src]
                }
            }
        }
        // Dijkstra的核心算法，找到最短路径，重新探路
        // 选择最短路径
        let min = INF
        let minIndex = -2
        for (let i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i]
                minIndex = i
            }
        }
        // 进入下一次循环
        if (minIndex === -2)
            src++
        else
            src = minIndex
        i++
    }
    return dist
}

let adj_matrix = [
    [0, 1, 1, 1, 1],
    [1, 0, 0, 1, 1],
    [1, 0, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [1, 1, 1, 1, 0],
]

console.log(Dijkstra(adj_matrix, 1))

// 输出点与各个点的距离：[1, 0, 2, 1, 1]