js 版迪杰斯特拉算法(Dijkstra)代码实现

迪杰斯特拉算法介绍:

Dijkstra 算法是一种计算从单个源到所有其他源的最短路径的贪心算法 这意味着我们可以用它来计算从图的一个顶点到其余各顶点的 最短路径

代码实现过程:

//  1: 图 grahp (用邻接矩阵表示)
//  2: 源顶点src(即算法开始的起点)

var graph = [
  // A  B  C  D  E  F
  [  0, 2, 4, 0, 0, 0], // A
  [  0, 0, 2, 4, 2, 0], // B
  [  0, 0, 0, 0, 3, 0], // C
  [  0, 0, 0, 0, 0, 2], // D
  [  0, 0, 0, 3, 0, 2], // E
  [  0, 0, 0, 0, 0, 0], // F
]

function Dijkstra(graph, src) {
  // 用来存储路径值
  let dist = [];
  let visited = [];
   // visited 用来存储顶点是否被访问过
  const length = graph.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) {
    // 去当前点到其他点的值
    let currentEdges = graph[i];
    // 标记当前点为已访问
    visited[i] = true;
    for(var j = 0; j < currentEdges.length; j++) {
      // 核心代码 即: 如果a -> b -> c 小于 a -> c 则更新dist[c]为dist[a] + dist[b]
      if (currentEdges[j] !== 0 && (currentEdges[j] + dist[i]  < dist[j])) {
        dist[j] = currentEdges[j] + dist[i];
      }
    }
    let min = INF;
    let minIndex = -2;
    // 取出当前点到其他点最小的点
    for(var f = 0; f < dist.length; f++) {
      if (!visited[f] && dist[f] < min) {
        min = dist[f];
        minIndex = f;
      }
    }
    // 设置最小点为下一个循环的点,继续寻找路径距离当前点最小的点
    i = minIndex;
  }
  return dist;
}

参考:
JavaScript实现最短路径算法