Wie funktioniert eine Breitensuche bei der Suche nach dem kürzesten Weg?

128

Ich habe einige Nachforschungen angestellt, und mir scheint ein kleiner Teil dieses Algorithmus zu fehlen. Ich verstehe, wie eine Breitensuche funktioniert, aber ich verstehe nicht, wie genau sie mich zu einem bestimmten Pfad bringt, anstatt mir nur zu sagen, wohin jeder einzelne Knoten gehen kann. Ich denke, der einfachste Weg, meine Verwirrung zu erklären, ist ein Beispiel:

Nehmen wir zum Beispiel an, ich habe ein Diagramm wie das folgende:

Geben Sie hier die Bildbeschreibung ein

Und mein Ziel ist es, von A nach E zu kommen (alle Kanten sind ungewichtet).

Ich fange bei A an, weil das mein Ursprung ist. Ich stelle A in die Warteschlange, gefolgt von der sofortigen Warteschlange A und der Erkundung. Dies ergibt B und D, da A mit B und D verbunden ist. Ich stelle also sowohl B als auch D in die Warteschlange.

Ich stelle B in die Warteschlange und erkunde es und stelle fest, dass es zu A (bereits erforscht) und C führt, also stelle ich C in die Warteschlange. Dann stelle ich D in die Warteschlange und stelle fest, dass es zu E führt, meinem Ziel. Ich stelle dann C in die Warteschlange und stelle fest, dass es auch zu E führt, meinem Ziel.

Ich weiß logischerweise, dass der schnellste Pfad A-> D-> E ist, aber ich bin mir nicht sicher, wie genau die Breitensuche hilft - wie sollte ich Pfade so aufzeichnen, dass ich nach Abschluss die Ergebnisse analysieren und sehen kann dass der kürzeste Weg A-> D-> E ist?

Beachten Sie außerdem, dass ich eigentlich keinen Baum verwende, sodass es keine "übergeordneten" Knoten gibt, sondern nur untergeordnete.

Jake
quelle
2
"Beachten Sie auch, dass ich keinen Baum verwende, sodass es keine" übergeordneten "Knoten gibt, sondern nur untergeordnete Knoten. Nun, Sie müssen den übergeordneten Knoten offensichtlich irgendwo speichern. Für DFS tun Sie dies indirekt über den Aufrufstapel, für BFS müssen Sie dies explizit tun. Ich fürchte, Sie können nichts dagegen tun :)
Voo

Antworten:

86

Technisch gesehen können Sie mit der Breitensuche (BFS) selbst nicht den kürzesten Pfad finden, einfach weil BFS nicht nach einem kürzesten Pfad sucht: BFS beschreibt eine Strategie für die Suche in einem Diagramm, sagt jedoch nicht, dass Sie danach suchen müssen etwas Besonderes.

Der Dijkstra-Algorithmus passt BFS an, damit Sie kürzeste Pfade aus einer Hand finden können.

Um den kürzesten Pfad vom Ursprung zu einem Knoten abzurufen, müssen Sie für jeden Knoten im Diagramm zwei Elemente verwalten: den aktuell kürzesten Abstand und den vorhergehenden Knoten im kürzesten Pfad. Anfangs sind alle Entfernungen auf unendlich und alle Vorgänger auf leer gesetzt. In Ihrem Beispiel setzen Sie den Abstand von A auf Null und fahren dann mit dem BFS fort. Bei jedem Schritt prüfen Sie, ob Sie die Entfernung eines Nachkommen verbessern können, dh die Entfernung vom Ursprung zum Vorgänger plus die Länge der Kante, die Sie untersuchen, ist geringer als die derzeit beste Entfernung für den betreffenden Knoten. Wenn Sie die Entfernung verbessern können, stellen Sie den neuen kürzesten Pfad ein und merken Sie sich den Vorgänger, über den dieser Pfad erfasst wurde. Wenn die BFS-Warteschlange leer ist, wählen Sie einen Knoten aus (in Ihrem Beispiel E) und durchlaufen Sie seine Vorgänger zurück zum Ursprung.

Wenn dies etwas verwirrend klingt, hat Wikipedia einen schönen Pseudocode-Abschnitt zum Thema.

dasblinkenlight
quelle
Danke dir! Ich hatte den Pseudocode zuvor gelesen, konnte ihn aber nicht verstehen. Ihre Erklärung ließ ihn für mich klicken
Jake
46
Ich möchte den folgenden Hinweis für Personen machen, die sich diesen Beitrag in Zukunft ansehen: Wenn die Kanten ungewichtet sind, muss nicht für jeden Knoten die "aktuell kürzeste Entfernung" gespeichert werden. Alles, was gespeichert werden muss, ist das übergeordnete Element für jeden erkannten Knoten. Während Sie einen Knoten untersuchen und alle seine Nachfolger in die Warteschlange stellen, setzen Sie einfach das übergeordnete Element dieser Knoten auf den zu untersuchenden Knoten (dies wird doppelt als "entdeckt" markiert). Wenn dieser übergeordnete Zeiger NUL / nil / None ist Für einen bestimmten Knoten bedeutet dies entweder, dass er noch nicht von BFS erkannt wurde, oder dass es sich um den Quell- / Stammknoten selbst handelt.
Shashank
@Shashank Wenn wir keine Distanz einhalten, wie würden wir dann die kürzeste Distanz kennen, bitte erklären Sie mehr.
Gaurav Sehgal
12
@gauravsehgal Dieser Kommentar gilt für Diagramme mit ungewichteten Kanten. BFS findet die kürzeste Entfernung einfach aufgrund seines radialen Suchmusters, bei dem Knoten in der Reihenfolge ihrer Entfernung vom Startpunkt berücksichtigt werden.
Shashank
13
Ein Tipp für Leser von @ Shashanks Kommentar: Ungewichtet und gleichmäßig gewichtet (z. B. haben alle Kanten ein Gewicht von 5) sind gleichwertig.
TWiStErRob
54

Wie oben erwähnt, kann BFS nur verwendet werden, um den kürzesten Pfad in einem Diagramm zu finden, wenn:

  1. Es gibt keine Schleifen

  2. Alle Kanten haben das gleiche Gewicht oder kein Gewicht.

Um den kürzesten Weg zu finden, müssen Sie nur von der Quelle aus starten und eine umfassende erste Suche durchführen und anhalten, wenn Sie Ihren Zielknoten gefunden haben. Das einzige zusätzliche, was Sie tun müssen, ist ein Array vor [n], in dem der vorherige Knoten für jeden besuchten Knoten gespeichert wird. Der vorherige der Quelle kann null sein.

Um den Pfad zu drucken, durchlaufen Sie einfach das vorherige [] Array von der Quelle bis zum Ziel und drucken die Knoten. DFS kann auch verwendet werden, um unter ähnlichen Bedingungen den kürzesten Pfad in einem Diagramm zu finden.

Wenn der Graph jedoch komplexer ist und gewichtete Kanten und Schleifen enthält, benötigen wir eine komplexere Version von BFS, dh den Dijkstra-Algorithmus.

javaProgrammer
quelle
1
Dijkstra, wenn keine -ve Gewichte sonst Bellman Ford Algo verwenden, wenn -ve Gewichte
Shaunak1111
Funktioniert BFS, um die kürzesten Pfade zwischen zwei Knoten zu finden?
Maria Ines Parnisari
34
@ JavaProgrammer, es ist nicht richtig. BFS kann auch verwendet werden, um den kürzesten Pfad in einem ungewichteten zyklischen Diagramm zu finden. Wenn ein Diagramm nicht gewichtet ist, kann BFS für SP angewendet werden, unabhängig davon, ob Schleifen vorhanden sind.
Andrei Kaigorodov
3
To print the path, simple loop through the previous[] array from source till you reach destination.Der vorherige Quellcode ist jedoch null. Ich denke, was du gemeint hast ist , backtrace from destination using the previous array until you reach the source.
Aandis
2
Warum funktioniert DFS Ihrer Meinung nach unter ähnlichen Bedingungen? Ist es für die DFS nicht möglich, einen naiven Umweg zu nehmen, um von den Knoten Start-> Ende zu gelangen, und Ihnen daher einen Pfad zu geben, der nicht der kürzeste ist?
James Wierzba
25

Aus dem Tutorial hier

"Es hat die äußerst nützliche Eigenschaft, dass das erste Mal, wenn ein Knoten besucht wird, der kürzeste Weg vom Quellknoten zu diesem Knoten ist, wenn alle Kanten in einem Diagramm ungewichtet sind (oder dasselbe Gewicht haben)."

acheron55
quelle
Dies ist gut für direkt erreichbare Knoten (1-> 2) (2 ist direkt von 1 aus erreichbar). Für nicht direkt erreichbare Knoten gibt es mehr Arbeit (1-> 2-> 3, 3 wird nicht direkt von 1 aus erreicht). Natürlich ist es immer noch wahr, wenn man individuell betrachtet, dh 1-> 2 & 2-> 3 einzeln sind kürzeste Wege.
Manohar Reddy Poreddy
10

Ich habe 3 Tage verschwendet und
letztendlich eine Grafikfrage gelöst,
die zum
Finden der kürzesten Entfernung
mit BFS verwendet wurde

Möchten Sie die Erfahrung teilen.

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

Ich habe 3 Tage verloren, als ich alle oben genannten Alternativen ausprobiert habe und immer wieder überprüft und erneut überprüft habe, ob
sie nicht das Problem sind.
(Versuchen Sie, Zeit damit zu verbringen, nach anderen Problemen zu suchen, wenn Sie keine Probleme mit den oben genannten 5 finden.)


Weitere Erklärung aus dem Kommentar unten:

      A
     /  \
  B       C
 /\       /\
D  E     F  G

Angenommen, oben ist Ihr Diagramm
nach unten.
Für A sind die Adjazenzen B & C.
Für B sind die Adjazenten D & E.
Für C sind die Adjazenzen F & G.

Angenommen, der Startknoten ist A.

  1. Wenn Sie A, B und C erreichen, beträgt die kürzeste Entfernung von A zu B & C 1

  2. Wenn Sie D oder E bis B erreichen, beträgt die kürzeste Entfernung zu A & D 2 (A-> B-> D).

in ähnlicher Weise ist A-> E 2 (A-> B-> E)

auch A-> F & A-> G ist 2

Also, anstatt 1 Abstand zwischen Knoten, wenn es 6 ist, dann multiplizieren Sie einfach die Antwort mit 6
Beispiel,
wenn Abstand zwischen jedem 1 ist, dann ist A-> E 2 (A-> B-> E = 1 + 1 )
Wenn der Abstand zwischen den beiden 6 beträgt, beträgt A-> E 12 (A-> B-> E = 6 + 6).

Ja, bfs kann jeden Pfad nehmen,
aber wir berechnen für alle Pfade

Wenn Sie von A nach Z gehen müssen, fahren wir alle Pfade von A zu einem Zwischen-I. Da es viele Pfade gibt, verwerfen wir alle bis auf den kürzesten Pfad bis I und fahren dann mit dem kürzesten Pfad bis zum nächsten Knoten J fort
, wenn Es gibt mehrere Pfade von I nach J, wir nehmen nur ein kürzestes
Beispiel,
nehmen an,
A -> I wir haben Abstand 5
(SCHRITT) nehmen an, I -> J wir haben mehrere Pfade mit den Abständen 7 und 8, da 7 am kürzesten ist
wir nehmen A -> J als 5 (A-> I am kürzesten) + 8 (am kürzesten jetzt) ​​= 13,
also ist A-> J jetzt 13,
wir wiederholen jetzt oben (SCHRITT) für J -> K und so weiter, bis wir bekommen bis Z.

Lesen Sie diesen Teil zwei- oder dreimal und zeichnen Sie auf Papier. Sie werden sicher das bekommen, was ich sage, viel Glück


Manohar Reddy Poreddy
quelle
Könnten Sie bitte näher erläutern, wie Sie es geschafft haben, den kürzesten Weg mit einer breiten ersten Suche zu finden? Eine breite erste Suche sucht hauptsächlich nach einem Knoten. Es kann n Pfade zu einem Zielknoten vom Quellknoten geben und bfs kann einen beliebigen Pfad nehmen. Wie bestimmen Sie den besten Weg?
Außenseiter
Ich habe 'mehr Erklärung' Teil zu der obigen Antwort hinzugefügt, lass es mich wissen, wenn das zufriedenstellend ist
Manohar Reddy Poreddy
1
Ich sehe, Sie versuchen, ein BFS für ein gewichtetes Diagramm auszuführen. Von den Entfernungen 7 & 8 warum hast du 8 gewählt? warum nicht 7? Was ist, wenn der 8-Knoten keine weiteren Kanten zum Ziel hat? Der Fluss muss dann 7 wählen.
Underdog
Gute Frage, positiv bewertet, ja, wir werfen nicht weg, wir verfolgen alle benachbarten Knoten, bis wir das Ziel erreichen. BFS funktioniert nur, wenn es nur konstante Abstände wie alle 7 oder alle 8 gibt. Ich habe einen generischen mit 7 & 8 angegeben, der auch als dijkstra-Algorithmus bezeichnet wird.
Manohar Reddy Poreddy
Entschuldigung, nicht sicher, was du meinst, siehe en.wikipedia.org/wiki/Dijkstra's_algorithm
Manohar Reddy Poreddy
2

Basierend auf acheron55 Antwort gab ich eine mögliche Implementierung hier .
Hier ist eine kurze Zusammenfassung davon:

Sie müssen lediglich den Pfad verfolgen, über den das Ziel erreicht wurde. Eine einfache Möglichkeit, dies zu tun, besteht darin, in den Queuegesamten Pfad zu pushen, der zum Erreichen eines Knotens verwendet wird, und nicht in den Knoten selbst.
Dies hat den Vorteil, dass die Warteschlange nach Erreichen des Ziels den Pfad enthält, der zum Erreichen des Ziels verwendet wird.
Dies gilt auch für zyklische Diagramme, bei denen ein Knoten mehr als ein übergeordnetes Element haben kann.

c0der
quelle
-6

Die folgende Lösung funktioniert für alle Testfälle.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

   public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);

            int testCases = sc.nextInt();

            for (int i = 0; i < testCases; i++)
            {
                int totalNodes = sc.nextInt();
                int totalEdges = sc.nextInt();

                Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();

                for (int j = 0; j < totalEdges; j++)
                {
                    int src = sc.nextInt();
                    int dest = sc.nextInt();

                    if (adjacencyList.get(src) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(src);
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    }


                    if (adjacencyList.get(dest) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(dest);
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    }
                }

                int start = sc.nextInt();

                Queue<Integer> queue = new LinkedList<>();

                queue.add(start);

                int[] costs = new int[totalNodes + 1];

                Arrays.fill(costs, 0);

                costs[start] = 0;

                Map<String, Integer> visited = new HashMap<String, Integer>();

                while (!queue.isEmpty())
                {
                    int node = queue.remove();

                    if(visited.get(node +"") != null)
                    {
                        continue;
                    }

                    visited.put(node + "", 1);

                    int nodeCost = costs[node];

                    List<Integer> children = adjacencyList.get(node);

                    if (children != null)
                    {
                        for (Integer child : children)
                        {
                            int total = nodeCost + 6;
                            String key = child + "";

                            if (visited.get(key) == null)
                            {
                                queue.add(child);

                                if (costs[child] == 0)
                                {
                                    costs[child] = total;
                                } else if (costs[child] > total)
                                {
                                    costs[child] = total;
                                }
                            }
                        }
                    }
                }

                for (int k = 1; k <= totalNodes; k++)
                {
                    if (k == start)
                    {
                        continue;
                    }

                    System.out.print(costs[k] == 0 ? -1 : costs[k]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
}
user3819236
quelle
4
Abgestimmt, weil die Frage nicht beantwortet wurde. Das einfache Einfügen eines Code-Snippets funktioniert unter SO nicht.
Rishabh Agrahari