Floyd/Warshall算法重建路徑，保存到列表中

Question

兩個簡單的問題和我的大腦不工作。我正在使用Floyd的算法並嘗試重建從頂點U到頂點V的路徑。 這裏是我的代碼來重建路徑。例如，令u = 0和v = 3，並且讓從0到3的最短路徑爲0,1,2,3。 但是我有兩個問題。我的pathList是類的實例變量：

1. 我想列表返回「0,1,2,3」，但它只返回「0,1,2」，或者如果我替換pathList。添加（u）與pathList.add（v），然後它返回 只有「1,2,3」我不知道如何使它返回包括兩個端點的整個 路徑。試圖把pathList.add（其他 頂點）將導致它複製每個中間頂點。
2. 當我再次調用該方法時，假設u = 3和v = 0，並且讓從3到0的最短路徑爲「3,0」（已經是最短路徑），它只會添加到我以前的列表中它我的錯誤從上面 「0,1,2,3」或「1,2,3,0」，當它應該是隻是「3,0」

任何幫助嗎？

Answer 1

請勿使用類變量，並創建包裝函數。

更詳細，你的函數改變這個簽名：

private List<Integer> findCheapestPathInner(int u, int v, pathList) 

（顯然也在改變它裏面的遞歸調用，以適應新的簽名），並創建另一個功能：

public List<Integer> findCheapestPath(int u, int v) { 
    List<Integer> pathList = new ArrayList<Integer>(); 
    pathList.add(u); 
    return findCheapestPathInner(u, v, pathList); 
}