Imprimir Bellman Ford caminho iterativamente
-
14-11-2019 - |
Pergunta
Eu tenho atualmente um Bellman Ford algoritmo de configurar e estou tentando imprimir o caminho para esse nó.Meu atual algoritmo é semelhante a esse:
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());
}
}
E isto é como eu sou de imprimi-lo.É recursiva, mas como eu poderia configurá-lo de modo que ele é repetitivo?Atualmente, estou recebendo um erro de estouro de pilha.
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+",");
}
}
Solução
Você tem o seu pai backlinks no caminho.Portanto, se você apenas siga os links novamente dentro de um loop while até a fonte, você já visitou o caminho inverso.Então, como você está visitando cada nó em um caminho, colocá-lo em um simples redimensionável recipiente (ArrayList funciona bem em Java) e, em seguida, inverter-lo e imprimi-lo para fora quando você está feito.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow