在求兩點之間的最短距離最常用的算法：Dijkstra 算法 和 Floyd-Warshall 算法。

1、Dijkstra 算法

解決單源有向圖最短路徑問題，時間復(fù)雜度為 O(n2)，n為頂點個數(shù)，如果是從其他頂點開始，那么在原有算法的基礎(chǔ)上再來一次循環(huán)，此時的時間復(fù)雜度為O(n3)。
特點是以起始點為中心向外層層擴展(廣度優(yōu)先搜索思想)，直到擴展到終點為止。

基本思想

通過 Dijkstra 計算圖G 中的最短路徑時，需要指定起點 s (即從頂點 s 開始計算)。
此外，引進兩個集合 S 和 U。S 的作用是記錄已求出最短路徑的頂點(以及相應(yīng)的最短路徑長度)，而 U 則是記錄還未求出最短路徑的頂點(以及該頂點到起點 s 的距離)。
初始時，S 中只有起點 s；U中是除s之外的頂點，并且U中頂點的路徑是"起點 s 到該頂點的路徑"。然后，從U中找出路徑最短的頂點，并將其加入到 S 中；接著，更新 U 中的頂點和頂點對應(yīng)的路徑。 然后，再從U中找出路徑最短的頂點，并將其加入到 S 中；接著，更新 U 中的頂點和頂點對應(yīng)的路徑。 ... 重復(fù)該操作，直到遍歷完所有頂點。

Dijkstra 算法 圖解

代碼實現(xiàn)：

const INF = Number.MAX_SAFE_INTEGER;
// 查找最近的點
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;
    }
  }
  return minIndex;
};
/** 
 * @param {圖：鄰接矩陣} graph 
 * @param {頂點索引} src 
 */
export const dijkstra = (graph, src) => {
  const dist = [];
  // 用于標(biāo)識頂點 src 至其他頂點的距離是否確定
  const visited = [];
  const { length } = graph; 
  for (let i = 0; i < length; i++) {
    dist[i] = INF;
    visited[i] = false;
  }
  dist[src] = 0;
  for (let i = 0; i < length - 1; i++) {
    const u = minDistance(dist, visited);
    // 標(biāo)識頂點 src 到此頂點的距離已經(jīng)確認(rèn)
    visited[u] = true;
    for (let v = 0; v < length; v++) {
      if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) {
        // 更新 dist
        dist[v] = dist[u] + graph[u][v];
      }
    }
  }
  return dist;
};

// test 
const 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 dist = dijkstra(graph, 0);
for (i = 0; i < dist.length; i++) {
    console.log(i + '\t\t' + dist[i]);
}
// result
0       0
1       2
2       4
3       6
4       4
5       6

2、Floyd-Warshall 算法

Floyd-Warshall 算法是一個經(jīng)典的動態(tài)規(guī)劃算法。
解決求所有頂點間的最短路徑問題，時間復(fù)雜度為O(n3)，n為頂點數(shù)。
可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。

基本思想

要求任意節(jié)點 i 到任意節(jié)點 j 的最短路徑，假設(shè) Dis(i,j) 為節(jié)點 u 到節(jié)點 v 的最短路徑的距離，對于每一個節(jié)點 k，我們檢查 Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點 k，Dis(i,j)中記錄的便是 i 到 j 的最短路徑的距離。

Floyd-Warshall 算法圖解

代碼實現(xiàn)：

export const floydWarshall = graph => {
  const dist = [];
  const { length } = graph;
  // 初始化鄰接矩陣
  for (let i = 0; i < length; i++) {
    dist[i] = [];
    for (let j = 0; j < length; j++) {
      if (i === j) {
        dist[i][j] = 0;
      } else if (!isFinite(graph[i][j])) {
        dist[i][j] = Infinity;
      } else {
        dist[i][j] = graph[i][j];
      }
    }
  }
  for (let k = 0; k < length; k++) {
    for (let i = 0; i < length; i++) {
      for (let j = 0; j < length; j++) {
        // 如果經(jīng)過下標(biāo)為 k 頂點路徑比原兩點間路徑更短，當(dāng)前兩點間權(quán)值設(shè)為更小的一個
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
};

// test
const INF = Infinity;
const graph = [
  [INF, 2, 4, INF, INF, INF],
  [INF, INF, 2, 4, 2, INF],
  [INF, INF, INF, INF, 3, INF],
  [INF, INF, INF, INF, INF, 2],
  [INF, INF, INF, 3, INF, 2],
  [INF, INF, INF, INF, INF, INF]
];

dist = floydWarshall(graph);

let s = '';
for (let i = 0; i < dist.length; ++i) {
  s = '';
  for (var j = 0; j < dist.length; ++j) {
    if (dist[i][j] === INF) s += 'INF ';
    else s += dist[i][j] + '   ';
  }
  console.log(s);
}
// result
0   2   4   6   4   6   
INF 0   2   4   2   4   
INF INF 0   6   3   5   
INF INF INF 0   INF 2   
INF INF INF 3   0   2   
INF INF INF INF INF 0

參考：
單源最短路徑演示