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

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 führt, anstatt mir nur zu sagen, wohin jeder einzelne Knoten gehen kann. Ich denke, der einfachste Weg, meine Verwirrung zu erklären, besteht darin, ein Beispiel zu geben:

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

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 reiht A in die Warteschlange ein, nehme dann sofort A aus der Warteschlange und untersuche es. Dies ergibt B und D, weil A mit B und D verbunden ist. Ich reiht also sowohl B als auch D ein.

Ich entferne B und erkunde es und finde heraus, dass es zu A (bereits erkundet) und C führt, also reiste ich C aus der Warteschlange. Dann entferne ich D und finde heraus, dass es zu E führt, meinem Ziel. Dann löse ich C aus der Warteschlange und finde heraus, 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 soll ich Pfade so aufzeichnen, dass ich die Ergebnisse analysieren und sehen kann, wenn ich fertig bin dass der kürzeste Weg A->D->E ist?

Beachten Sie auch, dass ich eigentlich keinen Baum verwende, es gibt also keine “übergeordneten” Knoten, sondern nur untergeordnete Knoten.

Technisch gesehen lässt Sie die Breitensuche (BFS) selbst nicht den kürzesten Weg finden, einfach weil BFS nicht nach einem kürzesten Weg sucht: BFS beschreibt eine Strategie zum Durchsuchen eines Graphen, aber es sagt nicht, dass Sie suchen müssen irgendetwas besonderes.

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

Um den kürzesten Pfad vom Ursprung zu einem Knoten abzurufen, müssen Sie zwei Elemente für jeden Knoten im Diagramm verwalten: seine aktuelle kürzeste Entfernung und den vorhergehenden Knoten im kürzesten Pfad. Zunächst werden alle Entfernungen auf unendlich gesetzt und alle Vorgänger auf leer. 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 kleiner 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 erinnern Sie sich an den Vorgänger, durch den dieser Pfad erfasst wurde. Wenn die BFS-Warteschlange leer ist, wählen Sie einen Knoten (in Ihrem Beispiel ist es E) und durchlaufen Sie seine Vorgänger zurück zum Ursprung. Dies würde Ihnen den kürzesten Weg geben.

Wenn dies etwas verwirrend klingt, hat Wikipedia eine nette Pseudocode-Abschnitt zum Thema.

Wie oben erwähnt, kann BFS nur verwendet werden, um den kürzesten Weg 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 Pfad zu finden, müssen Sie lediglich bei der Quelle beginnen und eine Breitensuche durchführen und anhalten, wenn Sie Ihren Zielknoten gefunden haben. Das einzige, was Sie zusätzlich tun müssen, ist ein vorheriges Array[n] die den vorherigen Knoten für jeden besuchten Knoten speichert. Der vorherige Wert von source kann null sein.

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

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

Aus Anleitung hier

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

Ich habe 3 Tage verschwendet
letztendlich eine Grafikfrage gelöst
benutzt für
kürzeste Distanz finden
mit BFS

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 damit verloren, alle oben genannten Alternativen auszuprobieren und oben immer wieder zu verifizieren und erneut zu verifizieren
sie sind nicht das Problem.
(Versuchen Sie, Zeit damit zu verbringen, nach anderen Problemen zu suchen, wenn Sie keine Probleme mit den oben genannten 5 finden).

Mehr Erklärung aus dem Kommentar unten:

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

Angenommen, oben ist Ihr Diagramm
Graph geht nach unten
Für A sind die Angrenzenden B & C
Für B sind die Angrenzenden D & E
Für C sind die Angrenzenden F & G

Angenommen, der Startknoten ist A

1. Wenn Sie A, nach, B & C erreichen, ist die kürzeste Entfernung von A nach B & C 1

2. Wenn Sie D oder E durch B erreichen, ist die kürzeste Entfernung zu A & D 2 (A->B->D)

ähnlich ist A->E 2 (A->B->E)

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

Also, jetzt statt 1 Abstand zwischen den Knoten, wenn es 6 ist, dann multipliziere einfach die Antwort mit 6
Beispiel,
wenn der Abstand zwischen jedem 1 ist, dann ist A->E 2 (A->B->E = 1+1)
wenn der Abstand zwischen jedem 6 ist, dann ist A->E 12 (A->B->E = 6+6)

ja, bfs können jeden weg gehen
aber wir rechnen für alle Pfade

Wenn Sie von A nach Z gehen müssen, fahren wir alle Pfade von A zu einem Zwischen-I, und da es viele Pfade geben wird, verwerfen wir alle bis auf den kürzesten Pfad bis I und fahren dann mit dem kürzesten Pfad voraus zum nächsten Knoten J fort
Wenn es wieder mehrere Wege von I nach J gibt, nehmen wir nur den kürzesten
Beispiel,
davon ausgehen,
A -> I wir haben Abstand 5
(SCHRITT) Angenommen, I -> J, wir haben mehrere Pfade mit den Abständen 7 und 8, da 7 der kürzeste 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 zu Z kommen

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

Nachdem ich diesen Thread nach einiger Zeit der Inaktivität besucht habe, aber da ich keine gründliche Antwort sehe, hier meine zwei Cent.

Die Breitensuche findet immer den kürzesten Pfad in einem ungewichteten Diagramm. Der Graph kann zyklisch oder azyklisch sein.

Siehe unten für Pseudocode. Dieser Pseudocode geht davon aus, dass Sie eine Warteschlange verwenden, um BFS zu implementieren. Es wird auch davon ausgegangen, dass Sie Scheitelpunkte als besucht markieren können und dass jeder Scheitelpunkt einen Entfernungsparameter speichert, der als unendlich initialisiert wird.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
if the start vertex is the end vertex, return 0
push the start vertex on the queue
while(queue is not empty)   
    dequeue one vertex (we’ll call it x) off of the queue
    if x is not marked as visited:
        mark it as visited
        for all of the unmarked children of x:
            set their distance values to be the distance of x + 1
            if the value of x is the value of the end vertex: 
                return the distance of x
            otherwise enqueue it to the queue
if here: there is no path connecting the vertices

Beachten Sie, dass dieser Ansatz nicht für gewichtete Graphen funktioniert – siehe dazu den Algorithmus von Dijkstra.

Basierend auf der Antwort von acheron55 habe ich hier eine mögliche Implementierung gepostet.
Hier eine kurze Zusammenfassung davon:

Alles, was Sie tun müssen, ist, den Weg zu verfolgen, auf dem das Ziel erreicht wurde. Eine einfache Möglichkeit, dies zu tun, besteht darin, in die zu schieben Queue der gesamte Pfad, der verwendet wird, um einen Knoten zu erreichen, und nicht der Knoten selbst.
Der Vorteil dabei ist, dass, wenn das Ziel erreicht wurde, die Warteschlange den Pfad hält, der verwendet wurde, um es zu erreichen.
Dies gilt auch für zyklische Graphen, bei denen ein Knoten mehr als einen Elternknoten haben kann.

Eine gute Erklärung, wie BFS kürzeste Pfade berechnet, begleitet von dem effizientesten einfachen BFS-Algorithmus, den ich kenne, und auch von funktionierendem Code, finden Sie im folgenden von Experten begutachteten Artikel:

https://queue.acm.org/detail.cfm?id=3424304

Das Papier erklärt, wie BFS einen Baum kürzester Pfade berechnet, der durch Elternzeiger pro Scheitelpunkt dargestellt wird, und wie ein bestimmter kürzester Pfad zwischen zwei beliebigen Scheitelpunkten aus den Elternzeigern wiederhergestellt werden kann. Die Erklärung von BFS nimmt drei Formen an: Prosa, Pseudocode und ein funktionierendes C-Programm.

Das Papier beschreibt auch “Efficient BFS” (E-BFS), eine einfache Variante des klassischen Lehrbuch-BFS, die dessen Effizienz verbessert. In der asymptotischen Analyse verbessert sich die Laufzeit von Theta(V+E) auf Omega(V). In Worten: Klassisches BFS läuft zeitlich immer proportional zur Anzahl der Knoten plus Anzahl der Kanten, während E-BFS manchmal nur proportional zur Anzahl der Knoten zeitmäßig läuft, die viel kleiner sein kann. In der Praxis kann E-BFS je nach Eingabegraph viel schneller sein. E-BFS bietet manchmal keinen Vorteil gegenüber klassischem BFS, aber es ist nie viel langsamer.

Bemerkenswerterweise scheint E-BFS trotz seiner Einfachheit nicht allgemein bekannt zu sein.