題意: 給定一個帶權有向圖，且指定起點、終點，問從起點至終點最多能有幾條不重疊的最短路徑。
解法: 先用floyd warshall算出任兩點間的最短路徑，接著判斷原圖中的每條邊(a,b)是否滿足"(s,a)的最短距離+(a,b)的權重+(b,t)的最短距離==(s,t)的最短距離"，若滿足則代表此邊是最短路徑的邊，將此邊加入新的網路圖中且容量為一，最後只需要在新建的網路圖中找出最大流即可。
TAG: Flow Network, Floyd Warshall, MaxFlow, Ford-Fulkerson
注意: 測資輸入的 adjacency matrix 中，對自己走到自己竟然會包含非0的值，所以必須給定edge[i][j] = 0, i == j。
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽