Floyd-Warshall algorithm

  • 用來尋找任意兩點間的最短路徑,可處理負邊。
  • 枚舉路徑j→k的中節點(i)。
  • DP轉移式:d[j][k] = min(d[j][k], d[j][i]+d[i][k]);
  • d[n][n] 存資料,n為節點數。
  • 時間複雜度:O(N^3)。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *