java - 迭代打印 Bellman Ford 路径

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 中运行良好），然后将其反转并在完成后将其打印出来。