Percorso più corto (meno nodi) per il grafico non ponderato

Question

Sto provando a costruire un metodo che restituisce il percorso più breve da un nodo a un altro in un grafico non ponderato. Ho considerato l'uso di Dijkstra, ma questo sembra un po 'eccessivo poiché voglio solo una coppia. Invece ho implementato una prima ricerca, ma il problema è che la mia lista di ritorno contiene alcuni dei nodi che non voglio - come posso modificare il mio codice per raggiungere il mio obiettivo?

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

In realtà il tuo codice non finirà in grafici ciclici, considera il grafico 1 -> 2 -> 1. Devi avere un array in cui è possibile contrassegnare quali nodi hai già visitato. E anche per ogni nodo è possibile salvare i nodi precedenti, da cui sei venuto. Quindi ecco il codice corretto:

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

Grazie Giolekva!

L'ho riscritto, refactoring alcuni:

• La raccolta di nodi visitati non deve essere una mappa.
• Per la ricostruzione del percorso, il nodo successivo poteva essere cercato, anziché il nodo precedente, eliminando la necessità di invertire le direzioni.

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

Non è davvero più semplice ottenere la risposta per una sola coppia che per tutte le coppie. Il solito modo per calcolare un percorso più breve è iniziare come fai, ma prendi nota ogni volta che si incontra un nuovo nodo e registri il nodo precedente sul percorso. Quindi, quando raggiungi il nodo target, è possibile seguire i backlink alla fonte e ottenere il percorso. Quindi, rimuovere il file directions.add(current) dal ciclo e aggiungi il codice qualcosa come il seguente

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

All'inizio e poi nel ciclo

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

E poi alla fine, basta costruire il directions Elenco all'indietro usando il backlinks carta geografica.

Answer 4

Ogni volta attraverso il tuo ciclo, chiami

directions.Add(current);

Invece, dovresti spostarlo in un posto dove sai davvero di voler quella voce.

Answer 5

È necessario includere il nodo genitore su ciascun nodo quando li metti in coda. Quindi puoi semplicemente leggere ricorsivamente il percorso da quell'elenco.

Supponi che vuoi trovare il percorso più breve da A a D in questo grafico:

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

Ogni volta che accendi un nodo, tieni traccia del modo in cui sei arrivato. Quindi al passaggio 1 b (a) e (a) viene messo sulla coda. Nel passaggio due B si spegne e C (B) viene messo sulla coda ecc. È quindi facile ritrovare la via del ritorno, riprendendo "all'indietro".

Il modo migliore è probabilmente fare un array fintanto che ci sono nodi e mantenere i collegamenti lì (che è quello che di solito faceva in IE. Dijkstra).