最短路径-Dijkstra算法

基于邻接矩阵matrixGraph实现
- 本质是贪心算法
  - 通过dist数组进行最小值记录并更新
  - 从中dist中不断取出“当前未访问过”的最小值的顶点索引u，第一次循环时必然取出起点(因为早就设为0)
    - 取出后标记为已访问
    - 根据索引u对这个顶点进行发散，得到许多索引v，在同时满足三种情况时更新dist内v的最小值
      - v未被访问过——如果已经被访问过，代表曾经当作最小被取出过，也就不可能有更小的情况
      - 在graph内有连接u和v的边，即不为0
      - 边的值加上u处已有最小距离小于 dist内v已存在的距离
  - 上面这个取出过程共进行len-1次，因此设n为1，在小于len时进入循环
    - 因为最后一个被取出之前，就已经在上一轮被发散更新完毕，故略过
- 需要一个dist记录

const dijkstra = (graph, start) => {
    const len = graph.length;
    const dist = new Array(len).fill(Infinity);
    dist[start] = 0;
    const visited = {};

    let n = 1;
    while(n++ < len) {
        let min = Infinity;
        let u = -1;
        dist.forEach((d, i) => {
            if (visited[i] !== 1 && d < min) {
                min = d;
                u = i;
            }
        })
        visited[u] = 1;
        for (v = 0; v < len; v++) {
            if (visited[v] !== 1 && graph[u][v] !== 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    return dist;
}


const matrixGraph = [
    [0, 2, 4, 0, 0, 0],
    [0, 0, 2, 4, 2, 0],
    [0, 0, 0, 0, 3, 0],
    [0, 0, 0, 0, 0, 2],
    [0, 0, 0, 3, 0, 2],
    [0, 0, 0, 0, 0, 0]
];

(() => {
     console.log(dijkstra(matrixGraph, 0));
})()

Keyboard shortcuts

最短路径-Dijkstra算法