Chemin le plus court (nombre de nœuds le plus court) pour un graphique non pondéré

Question

J'essaie de créer une méthode qui renvoie le chemin le plus court d'un nœud à un autre dans un graphique non pondéré. J'ai considéré l'utilisation de Dijkstra mais cela semble un peu exagéré puisque je ne veux qu'une paire. Au lieu de cela, j'ai mis en place une recherche de première grandeur, mais le problème est que ma liste de retour 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; 
} 

Answer 1

En fait votre code ne finira pas dans les graphiques cycliques, considérez le graphique 1 -> 2 -> 1. Vous devez avoir un tableau où vous pouvez marquer quel nœud vous avez déjà visité. Et aussi pour chaque nœud, vous pouvez sauvegarder les nœuds précédents, d'où vous venez. Donc, voici le code correct:

 
private Map<Node, Boolean>> vis = new HashMap<Node, Boolean>(); 

private Map<Node, Node> prev = new HashMap<Node, Node>(); 

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

Answer 2

Chaque fois que par votre boucle, vous appelez

directions.Add(current); 

Au lieu de cela, vous devez déplacer que dans un endroit où vous savez vraiment vous voulez que l'entrée.

Answer 3

Il n'est vraiment pas plus simple d'obtenir la réponse pour une seule paire que pour toutes les paires. La façon habituelle de calculer un chemin le plus court est de commencer comme vous le faites, mais faites une note chaque fois que vous rencontrez un nouveau nœud et enregistrez le nœud précédent sur le chemin. Ensuite, lorsque vous atteignez le nœud cible, vous pouvez suivre les backlinks vers la source et obtenir le chemin. Alors, retirez le directions.add(current) de la boucle, et ajouter quelque chose de code comme le suivant

Map<Node,Node> backlinks = new HashMap<Node,Node>(); 

au début, puis dans la boucle

if (!backlinks.containsKey(node)) { 
    backlinks.add(node, current); 
    q.add(node); 
} 

puis à la fin, juste construire la liste directions dans vers l'arrière en utilisant la carte backlinks.

Answer 4

Vous devez inclure le noeud parent à chaque noeud lorsque vous le placez dans votre file d'attente. Ensuite, vous pouvez simplement lire récursivement le chemin de cette liste.

que vous voulez trouver le chemin le plus court de A à D dans ce graphique:

 /B------C------D 
/    | 
A    /
    \   /
    \E--------- 

Chaque fois que vous ENQUEUE un nœud, garder une trace de la façon dont vous avez ici. Donc, à l'étape 1, B (A) E (A) est placé dans la file d'attente. Dans la deuxième étape, B est retiré et C (B) est mis dans la file d'attente, etc. Il est alors facile de retrouver votre chemin, juste en reculant "en arrière".

Le meilleur moyen est probablement de faire un tableau tant qu'il y a des nœuds et de garder les liens là-bas, (ce qui est généralement fait dans les Dijkstra).

Answer 5

Merci Giolekva!

Je réécrite, refactorisation quelques-uns:

• La collection de nœuds visités ne doit pas être une carte.
• Pour la reconstruction de chemin, le nœud suivant pourrait être recherché, au lieu du nœud précédent, ce qui élimine le besoin d'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; 
}