Najkrótsza ścieżka (najmniej węzłów) dla nieważonego wykresu

Question

Próbuję zbudować metodę, która zwraca najkrótszą ścieżkę z jednego węzła do drugiego na nieważonym wykresie. Zastanawiałem się nad użyciem Dijkstry, ale wydaje mi się to nieco przesadzone, ponieważ chcę tylko jednej pary. Zamiast tego zaimplementowałem szerokie wyszukiwanie, ale problem polega na tym, że moja lista zwrotów zawiera niektóre węzły, których nie chcę - w jaki sposób mogę zmodyfikować mój kod, aby osiągnąć mój cel?

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

W rzeczywistości Twój kod nie zostanie ukończony na wykresach cyklicznych, należy rozważyć wykres 1 -> 2 -> 1. Musisz mieć tablicę, w której możesz zgłosić, który węzeł już odwiedziłeś. A także dla każdego węzła można zapisać poprzednie węzły, z których przyszedłeś. Więc tutaj jest poprawny kod:

 
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

Za każdym razem, za pośrednictwem pętli zadzwonić

directions.Add(current); 

Zamiast tego, że należy przenieść do miejsca, gdzie naprawdę wiesz chcesz tego wpisu.

Answer 3

To naprawdę nie jest prostsze, aby uzyskać odpowiedź tylko dla jednej pary niż dla wszystkich par. Najczęstszym sposobem obliczania najkrótszej ścieżki jest rozpoczynanie tak, jak robisz, ale zanotuj za każdym razem, gdy napotkasz nowy węzeł i zapisz poprzedni węzeł na ścieżce. Następnie, po dotarciu do węzła docelowego, można śledzić linki zwrotne do źródła i uzyskać ścieżkę. Tak, usuń directions.add(current) z pętli i dodać kod coś jak poniżej

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

na początku, a następnie w pętli

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

a potem w końcu, po prostu skonstruowania listy w directions wstecz za pomocą mapy backlinks.

Answer 4

Musisz dołączyć węzeł nadrzędny do każdego węzła, gdy umieścisz je w swojej kolejce. Następnie możesz po prostu rekurencyjnie odczytać ścieżkę z tej listy.

Powiedzmy, że chcesz znaleźć najkrótszą drogę od A do D w tym wykresie:

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

Każdorazowe enqueue węzeł, śledzić sposób, w jaki tu mamy. Tak więc w kroku 1 B (A) E (A) zostaje umieszczony w kolejce. W kroku drugim B zostaje odjęty, a C (B) zostaje umieszczony w kolejce itp. Wtedy łatwo jest znaleźć drogę powrotną, po prostu powtarzając "wstecz".

Najlepszym sposobem jest prawdopodobnie utworzenie tablicy, o ile istnieją węzły i utrzymywanie tam odnośników (co zwykle jest wykonywane np. W Dijkstrze).

Answer 5

Dziękuję Giolekva!

przepisałem go, refactoring pewne:

• Zbiór odwiedzanych węzłów nie musi być mapą.
• Do rekonstrukcji ścieżki można było wyszukać następny węzeł zamiast poprzedniego węzła, eliminując potrzebę cofania kierunków.

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