Floyd-Warshall algorithm

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

分享文章
0 Shares
1 comment
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

You May Also Like

Set (集合)

Set 是一個儲存資料的容器,例如陣…

位元運算

幹嘛學位元運算? 位元運算比乘法、除…