Wie berechnet man den kürzesten Pfad zwischen zwei Knoten in einem Diagramm, in dem Quelle und Ziel identisch sind?

Question

Wie berechnet man den kürzesten Pfad zwischen zwei Knoten in einem Diagramm, in dem Quelle und Ziel identisch sind?

Graph:

A->B(5) 
A->D(5) 
A->E(7) 
B->C(4) 
C->D(8) 
C->E(2) 
D->C(8) 
D->E(6) 
E->B(3) 

zum Beispiel, was ist der kürzeste Weg zwischen B und B? Ich habe versucht, dijkstra zu verwenden, aber nicht funktioniert, es gibt immer B-> B im ersten Schritt zurück.

richtig am: B-> C-> E-> B

Answer 1

Split den Scheitel in zwei: B1 und B2, wobei alle Kanten, die in B in der ursprünglichen Graph gestartet werden in B1 beginnen; Alle Kanten, die in B enden, enden in B2.

Danach können Sie Dijkstra ausführen, um den kürzesten Pfad von B1 nach B2 im modifizierten Diagramm zu finden.

Hinweis: Wenn Sie alle Pfade im Diagramm beibehalten möchten, fügen Sie eine zusätzliche Kante B2-> B1 hinzu. Das ändert nicht das Ergebnis für Ihre Zyklus Suche, und alle Pfade in der ursprünglichen und modifizierten Grafik werden gleichwertig