Imprimer Bellman Chemin de Ford itérativement
-
14-11-2019 - |
Question
J'ai actuellement un algorithme Bellman Ford configuré et j'essaie d'imprimer le chemin de ce nœud.Mon algorithme actuel est comme ceci:
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());
}
}
Et c'est comme ça que je l'imprime.Il est récursif mais comment puis-je le mettre en place pour qu'il soit itératif?Je reçois actuellement une erreur de dépassement de pile.
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+",");
}
}
La solution
You have your parent backlinks in path. So if you just follow those links back inside a while loop until you the source, you'll have visited the path in reverse. So as you are visiting each node in a path, put it into a simple resizable container (ArrayList works well in Java), and then reverse it and print it out when you are done.
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow