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

image.png

我们来看看如何找到顶点A和其余顶点之间的最短路径。但首先，我们需要声明表示上图的邻接矩阵，如下所示。

let graph = [
        [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],
      ];

const INF = Number.MAX_SAFE_INTEGER;

      const dijkstra = (graph, src) => {
        const dist = [];
        const visited = [];
        const { length } = graph;
        for (let i = 0; i < length; i++) {
          // {1}
          dist[i] = INF;
          visited[i] = false;
        }
        dist[src] = 0; // {2}
        /** 要不断寻找没有被访问过且距离源点最近的点，有n个顶点
         *  就要寻找n-1次，找到点之后，对其邻接点进行松弛
         *  当剩下一个点的时候，这个点已经没有其他需要松弛的邻接点了。此时从源点到这个点的距离就是最短距离
         * */
        for (let i = 0; i < length - 1; i++) {
          // {3}
          const u = minDistance(dist, visited); // {4}
          visited[u] = true; // {5}
          for (let v = 0; v < length; v++) {
            if (
              !visited[v] &&
              graph[u][v] !== 0 &&
              dist[u] !== INF &&
              dist[u] + graph[u][v] < dist[v]
            ) {
              // {6}
              dist[v] = dist[u] + graph[u][v]; // {7}
            }
          }
        }
        console.log(dist);
        return dist; // {8}
      };
    
     //要计算顶点间的minDistance，就要搜索dist数组中的最小值，返回它在数组中的索引。
      const minDistance = (dist, visited) => {
        let min = INF;
        let minIndex = -1;
        for (let v = 0; v < dist.length; v++) {
          if (visited[v] === false && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
          }
        }
        console.log('minIndex:', minIndex)
        return minIndex;
      };

      dijkstra(graph, 0);

下面是对算法过程的描述。
❑ 行{1}：首先，把所有的距离（dist）初始化为无限大（JavaScript最大的数INF =Number.MAX_SAFE_INTEGER），将visited[]初始化为false。
❑ 行{2}：然后，把源顶点到自己的距离设为0。
❑ 行{3}：接下来，要找出到其余顶点的最短路径。
❑ 行{4}：为此，我们需要从尚未处理的顶点中选出距离最近的顶点。
❑ 行{5}：把选出的顶点标为visited，以免重复计算。
❑ 行{6}：如果找到更短的路径，则更新最短路径的值（行{7}）。
❑ 行{8}：处理完所有顶点后，返回从源顶点（src）到图中其他顶点最短路径的结果。