Anzahl der kürzesten Pfade in einem Diagramm

Question

Ich muss die Anzahl aller Pfade zwischen zwei Knoten eines Diagramms mithilfe von BFS finden. Ich denke, die Antwort auf meine Frage finden Sie hier:

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

Aber ich verstehe nicht ganz, es. Könnte jemand bitte den Algorithmus mit anderen Worten niederschreiben, damit ich ihn besser verstehen kann?

Answer 1

Nehmen wir an, Sie müssen von src zu dest gehen.

Mit jedem Knoten x assoziieren zwei Werte count und val, count ist die Nummer des kürzesten Pfads von src zu x und val ist die kürzeste Entfernung von src zu x. Pflegen Sie auch eine besuchte Variable, die angibt, ob der Knoten zum ersten Mal angekommen ist oder nicht.

Anwenden üblichen BFS-Algorithmus

Initialize u = src 
visited[u] = 1,val[u] = count[u] = 1 
For each child v of u, 
    if v is not visited 

Ein Knoten erstes Mal besucht wird, so dass es nur ein Pfad von der Quelle über u bis jetzt hat, so kürzester Weg bis zu v 1 + kürzestem Weg bis u und Anzahl Möglichkeiten, v über den kürzesten Pfad zu erreichen, sind mit count [u] identisch, da du 5 Wege von der Quelle aus haben kannst, dann können nur diese 5 Wege bis zu v erweitert werden, wenn v zum ersten Mal über u gefunden wird, also

val[v] = val[u]+1,  
count[v] = count[u], 
visited[v] = 1 

if v is visited 

Wenn v bereits besucht wird, was bedeutet, gibt es einen anderen Weg bis v über einige andere v ertices, dann drei Fälle entstehen:

1 :if val[v] == val[u]+1 

wenn Strom val [v], die über einen anderen Pfad bis v dist ist gleich val [u] + 1, das heißt, wir haben gleich kürzeste Distanzen zum Erreichen v Strom unter Verwendung von Weg durch u und der andere Weg bis v, dann bleibt die kürzeste Entfernung bis zu v gleich, aber die Anzahl der Wege erhöht sich um die Anzahl der Wege, die du erreichst.

count[v] = count[v]+count[u] 

2: val[v] > val[u]+1 

Wenn Strompfad erreicht v kleiner als vorheriger Wert von val [v], dann val [v] wird Strompfad gespeichert und COUNT [v] ist auch

val[v] = val[u]+1 
count[v] = count[u] 

Die dritte aktualisiert Wenn der aktuelle Pfad größer als der vorherige Pfad ist, müssen in diesem Fall die Werte von val [v] und count [v] nicht geändert werden.

Diesen Algorithmus ausführen, bis das BFS abgeschlossen ist. Am Ende enthält val [dest] die kürzeste Entfernung von der Quelle und count [dest] die Anzahl der Wege von src zu dest.