Problème avec la traversée de graphe

Question

J'ai implémenté un algorithme de traversée de graphe qui trouve un chemin entre deux noeuds dans le graphe. Le problème est qu'il ne trouve un chemin pour certaines requêtes quand je sais qu'il ya un chemin entre chaque nœud

public List getDirectRoute(Node start, Node end) 
{ 
    //Uses Dijkstras 
    List<Node> vis = new LinkedList<Node>(); 
    Map<Node,Node> prev = new HashMap<Node,Node>(); // Records the previous Node 

    List<Node> route = new LinkedList<Node>(); //Will hold the final route 
    Queue<Node> queue = new LinkedList<Node>(); // Used for the algorithm 

    Node current = start; 
    queue.add(current); 
    vis.add(current); 

    while(!queue.isEmpty()) 
    { 
     current = queue.remove(); 

     if(current.equals(end)) 
     { 
      break; 
     }else 
     { 
      for(Node node : successors(current)) 
      { 
       if(node.equals(vertices.get(0))) 
       { 
        continue; 
       } 
       if(!vis.contains(node)) 
       { 
        queue.add(node); 
        vis.add(node); 
        prev.put(node, current); 
       } 
      } 

      } 
    } 

    if (!current.equals(end)) 
    { 
     System.out.println("No route available"); 
    } 

    for(Node node = end; node != null; node = prev.get(node)) 
    { 
     route.add(node); 

    } 
    return route; 


} 

Suis-je manque quelque chose dans l'algorithme? J'ai exécuté le débogueur et mais je ne peux pas trouver le problème

Answer 1

Il semble que vous utilisiez une recherche de largeur au lieu de l'algorithme de Dijkstra pour trouver un chemin du début à la fin. J'ai supposé que les successeurs renvoient les nœuds que le courant peut traverser et que les nœuds vertices.get (0) signifient les nœuds qui n'ont pas de bord externe vers d'autres nœuds. Dans cet esprit, il semble que votre code devrait fonctionner correctement. Donc je dois dire que c'est soit la méthode de votre successeur qui fonctionne mal ou que vous avez ajouté des sommets qui ont des arêtes aux sommets (0) (bien que cela ne puisse contenir qu'un seul nœud).

Vous pourriez obtenir une meilleure réponse si nous savions ce que les successeurs ont fait et ce que vous stockez dans les sommets.

Answer 2

Je sais que vous essayez simplement de faire fonctionner votre code, probablement pas à la recherche d'une bibliothèque. Mais FYI, vous pouvez regarder JGraphT, qui est une bibliothèque de graphes pour Java. Il y a une solide implémentation de Dijkstra, entre autres choses.