Ruta más corta (menos nodos) para gráficos no ponderados

Question

Estoy intentando crear un método que devuelva la ruta más corta de un nodo a otro en un gráfico no ponderado. Consideré el uso de Dijkstra, pero esto parece un poco exagerado ya que solo quiero un par. En su lugar, he implementado una búsqueda de amplitud, pero el problema es que mi lista de devolución contiene algunos de los nodos que no quiero, ¿cómo puedo modificar mi código para lograr mi objetivo?

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 realidad, su código no terminará en gráficos cíclicos, considere el gráfico 1 -> 2 -> 1. Debe tener alguna matriz donde puede marcar qué nodo ha visitado ya. Y también para cada nodo puede guardar nodos previos, de donde proviene. Así que aquí está el código correcto:

 
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

Cada vez que a través de su bucle, que llaman

directions.Add(current); 

su lugar, debe mover eso a un lugar donde realmente sabe que quiere que la entrada.

Answer 3

Realmente no es más sencillo obtener la respuesta para un solo par que para todos los pares. La forma habitual de calcular una ruta más corta es comenzar como lo hace, pero tome nota siempre que encuentre un nuevo nodo y grabe el nodo anterior en la ruta. Luego, cuando llegue al nodo de destino, puede seguir los enlaces de retroceso hasta la fuente y obtener la ruta. Por lo tanto, eliminar el directions.add(current) del bucle, y agregar código similar al siguiente

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

en el comienzo y luego en el bucle

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

y luego, al final, acaba de construir la lista directions en hacia atrás usando el mapa backlinks.

Answer 4

Debe incluir el nodo padre en cada nodo cuando los coloca en su cola. Luego puede leer recursivamente la ruta desde esa lista.

decir que quiere encontrar el camino más corto desde la A a la D en este gráfico:

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

Cada vez que un nodo de encolar, no perder de vista la forma de llegar aquí. Por lo tanto, en el paso 1 B (A) E (A) se pone en la cola. En el paso dos, B se quita de la cola y C (B) se pone en la cola, etc. Entonces es fácil encontrar el camino de regreso, simplemente repitiendo "hacia atrás".

La mejor manera es, probablemente, hacer una matriz, siempre y cuando haya nodos y mantener los enlaces allí, (que normalmente se hace, por ejemplo, en Dijkstra).

Answer 5

Gracias Giolekva!

me volvió a escribir, algunos refactorización:

• La colección de nodos visitados no tiene que ser un mapa.
• Para la reconstrucción de ruta, el siguiente nodo podría buscarse, en lugar del nodo anterior, eliminando la necesidad de invertir las direcciones.

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; 
}