學習JavaScript數據結構與算法（第2版）：9.5 最短路徑算法_Loiane Grone

設想你要從街道地圖上的A點，通過可能的最短路徑到達B點。舉例來說，從洛杉磯的聖莫尼卡大道到好萊塢大道，如下圖所示：

這種問題在生活中非常常見，我們（特別是生活在大城市的人們）會求助於蘋果地圖、谷歌地圖、Waze等應用程序。當然，我們也有其他的考慮，如時間或路況，但根本的問題仍然是：從A到B的最短路徑是什麼？

我們可以用圖來解決這個問題，相應的算法被稱為最短路徑。本節我們將介紹兩種非常著名的算法，即Dijkstra算法和Floyd-Warshall算法。

9.5.1　Dijkstra算法

Dijkstra算法是一種計算從單個源到所有其他源的最短路徑的貪心算法（你可以在第11章瞭解到更多關於貪心算法的內容），這意味著我們可以用它來計算從圖的一個頂點到其餘各頂點的最短路徑。

考慮下圖：

我們來看看如何找到頂點A和其餘頂點之間的最短路徑。但首先，我們需要聲明表示上圖的鄰接矩陣，如下所示：

var graph = [[0, 2, 4, 0, 0, 0],
             [0, 0, 1, 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]];

現在，通過下面的代碼來看看Dijkstra算法是如何工作的：

this.dijkstra = function(src) {
  var dist = , visited = ,
    length = this.graph.length;

  for (var i = 0; i < length; i++) { //{1}
    dist[i] = INF;
    visited[i] = false;
  }
  dist[src] = 0; //{2}

  for (var i = 0; i < length-1; i++) { //{3}
    var u = minDistance(dist, visited); //{4}
    visited[u] = true; //{5}

    for (var v = 0; v < length; v++) {
      if (!visited[v] &&
      this.graph[u][v] != 0 && dist[u] != INF &&
      dist[u] + this.graph[u][v] < dist[v]) { //{6}
        dist[v] = dist[u] + this.graph[u][v]; //{7}
      }
    }
  }
  return dist; //{8}
};

下面是對算法過程的描述。

行{1}：首先，把所有的距離（dist）初始化為無限大（JavaScript最大的數INF = Number. MAX_SAFE_INTEGER），將visited初始化為false。
行{2}：然後，把源頂點到自己的距離設為0。
行{3}：接下來，要找出到其餘頂點的最短路徑。
行{4}：為此，我們需要從尚未處理的頂點中選出距離最近的頂點。
行{5}：把選出的頂點標為visited，以免重複計算。
行{6}：如果找到更短的路徑，則更新最短路徑的值（行{7}）。
行{8}：處理完所有頂點後，返回從源頂點（src）到圖中其他頂點最短路徑的結果。

要計算頂點間的minDistance，就要搜索dist數組中的最小值，返回它在數組中的索引：

var minDistance = function(dist, visited) {
  var min = INF, minIndex = -1;

  for (var v = 0; v < dist.length; v++) {
    if (visited[v] == false && dist[v] <= min) {
      min = dist[v];
      minIndex = v;
    }
  }
  return minIndex;
};

對本節開始的圖執行以上算法，會得到如下輸出：

　也可以修改算法，將最短路徑的值和路徑一同返回。

9.5.2　Floyd-Warshall算法

Floyd-Warshall算法是一種計算圖中所有最短路徑的動態規划算法（你可以在第11章瞭解到更多關於動態規划算法的內容）。通過該算法，我們可以找出從所有源到所有頂點的最短路徑。

Floyd-Warshall算法實現如下：

this.floydWarshall = function {
  var dist = ,
    length = this.graph.length,
    i, j, k;

  for (i = 0; i < length; i++) { //{1}
    dist[i] = ;
    for (j = 0; j < length; j++) {
      dist[i][j] = this.graph[i][j];
    }
  }

  for (k = 0; k < length; k++) { //{2}
    for (i = 0; i < length; i++) {
      for (j = 0; j < length; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) { //{3}
          dist[i][j] = dist[i][k] + dist[k][j]; //{4}
        }
      }
    }
  }
  return dist;
};

下面是對算法過程的描述。

行{1}：首先，把dist數組初始化為每個頂點之間的權值，因為i到j可能的最短距離就是這些頂點間的權值。
行{2}：通過k，得到i途徑頂點0至k，到達j的最短路徑。
行{3}：判斷i經過頂點k到達j的路徑是否比已有的最短路徑更短。
行{4}：如果是更短的路徑，則更新最短路徑的值。

行{3}是Floyd-Warshall算法的核心。對本節開始的圖執行以上算法，會得到如下輸出：

0   2   3   6   4   6
INF 0   1   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

其中，INF代表頂點i到j的最短路徑不存在。

對圖中每一個頂點執行Dijkstra算法，也可以得到相同的結果。

9.5.1 Dijkstra算法

9.5.2 Floyd-Warshall算法

9.5.1　Dijkstra算法

9.5.2　Floyd-Warshall算法