JS使用Dijkstra算法求解最短路徑

/**
 * Dijkstra算法：?jiǎn)卧醋疃搪窂? * 思路：
 * 1. 將頂點(diǎn)分為兩部分：已經(jīng)知道當(dāng)前最短路徑的頂點(diǎn)集合Q和無(wú)法到達(dá)頂點(diǎn)集合R。
 * 2. 定義一個(gè)距離數(shù)組（distance）記錄源點(diǎn)到各頂點(diǎn)的距離，下標(biāo)表示頂點(diǎn)，元素值為距離。源點(diǎn)（start）到自身的距離為0，源點(diǎn)無(wú)法到達(dá)的頂點(diǎn)的距離就是一個(gè)大數(shù)（比如Infinity）。
 * 3. 以距離數(shù)組中值為非Infinity的頂點(diǎn)V為中轉(zhuǎn)跳點(diǎn)，假設(shè)V跳轉(zhuǎn)至頂點(diǎn)W的距離加上頂點(diǎn)V至源點(diǎn)的距離還小于頂點(diǎn)W至源點(diǎn)的距離，那么就可以更新頂點(diǎn)W至源點(diǎn)的距離。即下面distance[V] + matrix[V][W] < distance[W]，那么distance[W] = distance[V] + matrix[V][W]。
 * 4. 重復(fù)上一步驟，即遍歷距離數(shù)組，同時(shí)無(wú)法到達(dá)頂點(diǎn)集合R為空。
 *
 * @param matrix 鄰接矩陣，表示圖
 * @param start 起點(diǎn)
 *
 *
 *
 * 如果求全圖各頂點(diǎn)作為源點(diǎn)的全部最短路徑，則遍歷使用Dijkstra算法即可，不過(guò)時(shí)間復(fù)雜度就變成O(n^3)了
 * */
function Dijkstra(matrix, start = 0) {
  const rows = matrix.length,//rows和cols一樣，其實(shí)就是頂點(diǎn)個(gè)數(shù)
    cols = matrix[0].length;
 
  if(rows !== cols || start >= rows) return new Error("鄰接矩陣錯(cuò)誤或者源點(diǎn)錯(cuò)誤");
 
  //初始化distance
  const distance = new Array(rows).fill(Infinity);
  distance[start] = 0;
 
  for(let i = 0; i < rows; i++) {
    //達(dá)到不了的頂點(diǎn)不能作為中轉(zhuǎn)跳點(diǎn)
    if(distance[i] < Infinity) {
      for(let j = 0; j < cols; j++) {
        //比如通過(guò)比較distance[i] + matrix[i][j]和distance[j]的大小來(lái)決定是否更新distance[j]。
        if(matrix[i][j] + distance[i] < distance[j]) {
          distance[j] = matrix[i][j] + distance[i];
        }
      }
      console.log(distance);
    }
  }
  return distance;
}
 
/**
 * 鄰接矩陣
 * 值為頂點(diǎn)與頂點(diǎn)之間邊的權(quán)值，0表示無(wú)自環(huán)，一個(gè)大數(shù)表示無(wú)邊(比如10000)
 * */
const MAX_INTEGER = Infinity;//沒(méi)有邊或者有向圖中無(wú)法到達(dá)
const MIN_INTEGER = 0;//沒(méi)有自環(huán)
 
const matrix= [
  [MIN_INTEGER, 9, 2, MAX_INTEGER, 6],
  [9, MIN_INTEGER, 3, MAX_INTEGER, MAX_INTEGER],
  [2, 3, MIN_INTEGER, 5, MAX_INTEGER],
  [MAX_INTEGER, MAX_INTEGER, 5, MIN_INTEGER, 1],
  [6, MAX_INTEGER, MAX_INTEGER, 1, MIN_INTEGER]
];
 
 
console.log(Dijkstra(matrix, 0));//[ 0, 5, 2, 7, 6 ]