Le chemin le plus court (moins de nœuds) pour les non pondérée graphique

Je suis en train de construire une méthode qui retourne le plus court chemin d'un nœud à l'autre, dans un graphe non pondéré. J'ai considéré que l'utilisation de Dijkstra, mais cela semble un peu exagéré car je veux seulement une paire. Au lieu de cela j'ai mis en place une largeur tout d'abord de recherche, mais le problème est que mon retour liste contient certains des nœuds que je ne veux pas - comment puis-je modifier mon code pour atteindre mon objectif?

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                    q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
    }
    return directions;
}

pourquoi vous ne voulez PAS que certains de ces nœuds?
pas tous d'entre eux appartiennent à un seul chemin le plus court itinéraire
ne Nœud de la classe remplacer equals et hashcode correctement?
Quand je faisais quelque chose comme ça sur une grille 2D, j'ai trouvé la Une* (Étoile) algorithme plus facile à comprendre.
Je pense que l'aide de l'algorithme de Dijkstra est la façon la plus simple. Vous faites passer les nœuds pour marquer leur coût et un autre passage de choisir l'itinéraire le plus court. Il semble que vous essayez de faire tout en une seule opération, je ne pense pas que se fait facilement avec cet algorithme.

OriginalL'auteur Robert | 2009-10-16

20

Réellement votre code ne sera pas fini dans cyclique de graphiques, de considérer le graphique 1 -> 2 -> 1. Vous devez disposer d'un tableau où vous pouvez pavillon du nœud que vous avez déjà visité. Et également, pour chaque nœud, vous pouvez enregistrer précédente nœuds, d'où vous venez. Voici donc le code est correct:
```
privé Map<Nœud, Boolean>> vis = new HashMap<Nœud, Boolean>(); 

privé Map<Nœud, Nœud> prev = new HashMap<Nœud, Nœud>(); 

Liste publique getDirections(Nœud de départ, le Noeud de finition){ 
Liste des directions = new LinkedList(); 
La file d'attente q = new LinkedList(); 
Nœud courant = début; 
q.ajouter(en cours); 
vis.mettre(en cours, true); 
while(!q.isEmpty()){ 
courant = q.remove(); 
si (actuelle.equals(terminer)){ 
break; 
}else{ 
pour(Nœud nœud courant.getOutNodes()){ 
if(!vis.contient(nœud)){ 
q.ajouter(node); 
vis.mettre(nœud, true); 
prev.mettre(nœud courant); 
} 
} 
} 
} 
if (!actuel.equals(terminer)){ 
Système..println("vous ne pouvez pas atteindre la destination"); 
} 
pour(Node node = finition; noeud != null; node = prev.get(nœud)) { 
les directions.ajouter(node); 
} 
les directions.reverse(); 
les directions de retour; 
} 
```
tu veux dire vis.get(nœud) == null bien sûr, sinon, il y a une exception de pointeur null
yep, je l'ai déjà changée avec la méthode contains. J'ai écrit ce code ici sans aucune IDE, donc il y aura peut être quelques fautes de frappe 🙂
c'est un très bon exemple - enfin, le déclic pour moi, de la façon de trouver le chemin le plus court et aussi les étapes
Je pense que cela ne fonctionnera pas pour le graphe suivant: A->C->D->F->D->F le chemin le plus court est le dernier mais prev[D] sera remplacé par C (au lieu d'Un), avant d'atteindre F. au retournés chemin (les directions) seront les suivants: A->C->D->F

OriginalL'auteur giolekva

Merci Giolekva!

Je l'ai réécrit, refactoring certains:

La collection de noeuds visités n'a pas à être une carte.
Pour le chemin de la reconstruction, le nœud suivant pourrait être considéré, à la place du nœud précédent, éliminant le besoin pour inverser les directions.

public List<Node> getDirections(Node sourceNode, Node destinationNode) {
//Initialization.
Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
Node currentNode = sourceNode;
//Queue
Queue<Node> queue = new LinkedList<Node>();
queue.add(currentNode);
/*
* The set of visited nodes doesn't have to be a Map, and, since order
* is not important, an ordered collection is not needed. HashSet is 
* fast for add and lookup, if configured properly.
*/
Set<Node> visitedNodes = new HashSet<Node>();
visitedNodes.add(currentNode);
//Search.
while (!queue.isEmpty()) {
currentNode = queue.remove();
if (currentNode.equals(destinationNode)) {
break;
} else {
for (Node nextNode : getChildNodes(currentNode)) {
if (!visitedNodes.contains(nextNode)) {
queue.add(nextNode);
visitedNodes.add(nextNode);
//Look up of next node instead of previous.
nextNodeMap.put(currentNode, nextNode);
}
}
}
}
//If all nodes are explored and the destination node hasn't been found.
if (!currentNode.equals(destinationNode)) {
throw new RuntimeException("No feasible path.");
}
//Reconstruct path. No need to reverse.
List<Node> directions = new LinkedList<Node>();
for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
directions.add(node);
}
return directions;
}

Cette méthode est mauvais, parce que, pour l'exemple suivant, le résultat sera mauvais. Pour la prochaine pairs1-2 1-3 2-5 getDirections("1","5") = "1","3"'

OriginalL'auteur Leif Bork

1

Il est vraiment pas plus simple d'obtenir la réponse pour une paire que pour toutes les paires. La manière habituelle pour calculer le chemin le plus court est de commencer comme vous le faites, mais faire une remarque à chaque fois que vous rencontrez un nouveau nœud et d'enregistrer le nœud précédent sur le chemin. Ensuite, lorsque vous atteignez le noeud cible, vous pouvez suivre les backlinks de la source et obtenir le chemin d'accès. Donc, supprimer la directions.add(current) de la boucle, et d'ajouter le code quelque chose comme ce qui suit
```
Map<Node,Node> backlinks = new HashMap<Node,Node>();
```
au début et puis dans la boucle
```
if (!backlinks.containsKey(node)) {
backlinks.add(node, current);
q.add(node);
}
```
et puis en fin de compte, juste à construire la directions liste à l'envers à l'aide de la backlinks carte.

OriginalL'auteur JaakkoK
0

À chaque fois par le biais de votre boucle, vous appelez
```
directions.Add(current);
```
Au lieu de cela, vous devez vous déplacer à un endroit où vous savez vraiment vous voulez que l'entrée.

comment peut-il savoir si il est nécessaire d'ajouter ou non?

OriginalL'auteur John Fisher
0

Vous devez inclure le nœud parent pour chaque nœud lorsque vous les mettez sur votre file d'attente. Ensuite, vous pouvez simplement récursivement lire le chemin d'accès à partir de cette liste.

Dites que vous voulez trouver le plus court chemin de A à D dans ce Graphique:
```
     /B------C------D
/                |
A                 /
\             /
\E---------
```
Chaque fois que vous mettre en file d'attente d'un nœud, de garder trace de la façon dont vous êtes arrivé ici.
Ainsi, dans l'étape 1 B(Un) E(Un) est mis dans la file d'attente. Dans l'étape B deux obtient retiré et C(B) est placé dans la file d'attente etc. Son facile à trouver votre chemin du retour à nouveau, juste par recursing "à l'envers".

Meilleur moyen est sans doute de faire un tableau aussi longtemps qu'il y a de nœuds et de garder les liens, il y, (qui est ce qui est fait habituellement dans ie. Dijkstra).

OriginalL'auteur Johan Benum Evensberget

Vous devez vous connecter pour publier un commentaire.