Ruta más corta (menos nodos) para un gráfico no ponderado

Question

Estoy intentando construir 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 cambio, he implementado una búsqueda de amplitud, pero el problema es que mi lista de regreso 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 una matriz donde pueda marcar qué nodos ya ha visitado. Y también para cada nodo, puede guardar nodos anteriores, de los cuales vino. 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

¡Gracias Giolekva!

Lo reescribí, refactorizando algunos:

• La colección de nodos visitados no tiene que ser un mapa.
• Para la reconstrucción de la ruta, el siguiente nodo podría buscar, en lugar del nodo anterior, eliminando la necesidad de revertir 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;
}

Answer 3

Realmente no es más simple 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 usted, pero tome una nota cada vez que encuentre un nuevo nodo y registre el nodo anterior en la ruta. Luego, cuando alcanza el nodo de destino, puede seguir los vínculos de retroceso a la fuente y obtener la ruta. Entonces, retire el directions.add(current) Desde el bucle, y agregue el código algo como lo siguiente

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

Al principio y luego en el bucle

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

Y luego, al final, solo construya el directions Lista en el revés usando el backlinks mapa.

Answer 4

Cada vez a través de tu bucle, llamas

directions.Add(current);

En cambio, debes mover eso a un lugar donde realmente sabes que quieres esa entrada.

Answer 5

Debe incluir el nodo principal en cada nodo cuando los coloque en su cola. Entonces puede leer recursivamente la ruta de esa lista.

Digamos que desea encontrar la ruta más corta de A a D en este gráfico:

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

Cada vez que enqueue un nodo, realice un seguimiento de la forma en que llegó aquí. Entonces, en el paso 1 b (a) e (a) se coloca en la cola. En el paso dos, se enoja y se coloca C (b) en la cola, etc. Es fácil encontrar el camino de regreso, simplemente recurre "al revés".

La mejor manera es probablemente hacer una matriz siempre que haya nodos y mantener los enlaces allí, (que generalmente es lo que generalmente se hace en IE. Dijkstra).