打印貝爾曼福特路徑迭代

Question

我目前有一個貝爾曼福特算法設置，我試圖打印該節點的路徑。我目前的算法是這樣的：

path = new int[totaledges]; 
path[source] = source; 
distance[source] = 0; 
String st = ""; 
for (int i = 0; i < totaledges; i++) 
    for (int j = 0; j < edges.size(); j++) { 
     int newDistance = distance[edges.get(j).getSource()] + edges.get(j).getWeight(); 
     //System.out.println(newDistance + " this is teh distance"); 
     if (newDistance < distance[edges.get(j).getDestination()]){ 
      distance[edges.get(j).getDestination()] = newDistance; 
      path[edges.get(j).getDestination()] = edges.get(j).getSource(); 
      //System.out.println(edges.get(j).getSource()); 
     } 
    } 

這就是我打印出來的方式。它是遞歸的，但我如何設置它以便迭代？我目前正在發生堆棧溢出錯誤。

static void printedges(int source, int i, int[] paths) 
{ 
    // print the array that is get from step 2 
    if(source!=i){ 
     printedges(source, paths[i], paths); 
    } 
    if(i == currentEdge){ 
     System.out.print(i); 
    } else{ 
     System.out.print(i+","); 
    } 
} 

Answer 1

你有你的父母的反向鏈接的路徑。所以如果你只是在一個while循環中追蹤這些鏈接，直到你找到源代碼，那麼你就會反向訪問這個路徑。因此，當您訪問路徑中的每個節點時，請將其放入一個簡單的可調整大小的容器（ArrayList在Java中運行良好），然後將其反轉並在完成後將其打印出來。