Печатать путь Беллмана Форда итеративно - PullRequest
Новая
       11

Печатать путь Беллмана Форда итеративно

0 голосов
/ 18 мая 2011

В настоящее время у меня настроен алгоритм Беллмана Форда, и я пытаюсь распечатать путь к этому узлу.Мой текущий алгоритм выглядит так: 

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+",");
    }
}

1 Ответ

0 голосов
/ 18 мая 2011

У вас есть родительские обратные ссылки в пути. Так что, если вы просто перейдете по этим ссылкам внутри цикла while, пока не найдете источник, вы пойдете по пути в обратном направлении. Поэтому, когда вы посещаете каждый узел в пути, поместите его в простой контейнер с изменяемым размером (ArrayList хорошо работает в Java), а затем разверните его и распечатайте, когда закончите.

...