僅使用鄰接矩陣的BFS最短路徑？

我正在試圖使用鄰接矩陣來實現Ford-Fulkerson/Edmonds-Karp。唯一不能編程的是使用BFS計算最短路徑的函數。看看最短路徑實際存在的功能是好的，但是有可能獲得最短路徑嗎？或者是獲得BFS的最短路徑使用某種父指針並向後遍歷以獲取路徑的唯一方法？僅使用鄰接矩陣的BFS最短路徑？

這裏是我的代碼，看看是否存在路徑：

public static boolean existsPathFromSourceToSinkInGf(int Gf[][]) 
{ 
    LinkedList<Integer> queue = new LinkedList<Integer>(); 
    queue.add(0); 

    while (!queue.isEmpty()) 
    { 
     int v = queue.remove(); 
     if (v == sink) return true; 
     for (int i = 0; i < 5; i++) 
     { 

      if (Gf[v][i] != 0) 
      { 
       if (!queue.contains((Integer)i)) 
       { 
        queue.add((Integer)i); 
       } 
      } 
     } 
    } 

    return false; 

    }

來源

2012-11-15 eivindml

是的，你應該使用'parent'並且回溯得到數組。由於你的頂點是整數，所以它可以用一個實際上是'int []'的映射來完成 - 其中'parent [i] =節點i的父節點' – amit

常見的方式做到這一點確實是保持每次解決一個節點，一旦你找到了你的路徑倒退時間父指針。

您還可以在隊列中明確記錄路徑。您可以創建自己的類，包含整數和一個類似「node 1-> node 3 - > ...」的字符串，而不是僅爲整個鏈表使用整數。它由於類和路徑的開銷而不太常用，但它避免了必須自行保留父指針，並且最終必須遍歷它們。

在一個側面說明2名備註您的代碼：

爲什麼它運行對於i = 0..5？
您檢查if (!queue.contains((Integer)i))，這樣您就不會在已存在的隊列上放置頂點。您還應該避免將頂點放在已從列表中移除的頂點上（嘗試維護一組訪問節點）。

來源

2012-11-16 13:56:52 Origin

僅使用鄰接矩陣的BFS最短路徑？

回答

相關問題