Was ist der schnellste Algorithmus zum Auffinden aller kürzesten Pfade in einem Diagramm mit geringer Dichte?

Was ist in einem ungewichteten, ungerichteten Graphen mit $V$ Ecken und $E$ Kanten, so dass $2V \gt E$ , der schnellste Weg, um alle kürzesten Pfade in einem Graphen zu finden? Kann es in schneller als Floyd-Warshall durchgeführt werden, was aber pro Iteration sehr schnell?$O(V^3)$

Wie wäre es, wenn das Diagramm gewichtet ist?

Da es sich um ein ungewichtetes Diagramm handelt, können Sie eine Breitensuche ( Breadth First Search, BFS) für jeden Scheitelpunkt im Diagramm ausführen . Mit jedem Durchlauf von BFS erhalten Sie die kürzesten Entfernungen (und Pfade) vom Startscheitelpunkt zu jedem anderen Scheitelpunkt. Die Zeitkomplexität für ein BFS beträgt O ( V + E ) = O ( V ), da E = O ( V ) in Ihrem spärlichen Diagramm ist. Wenn Sie es V- mal ausführen, erhalten Sie eine O ( V 2 ) -Zeitkomplexität.$v$$O(V + E) = O(V)$$E = O(V)$$V$$O(V^2)$

Für einen gewichteten gerichteten Graphen ist der von Yuval vorgeschlagene Johnson-Algorithmus für spärliche Graphen am schnellsten. Es wird $O(V^2\log V + VE)$ was sich in Ihrem Fall als herausstellt $O(V^2\log V)$. Für ein gewichtetes ungerichtetes Diagramm können Sie entweder den Dijkstra-Algorithmus ausführenvon jedem Knoten aus, oder ersetzen Sie jede ungerichtete Kante durch zwei entgegengesetzt gerichtete Kanten, und führen Sie den Johnson-Algorithmus aus. In beiden Fällen werden die gleichen aysmptotischen Zeiten wie in Johnsons Algorithmus für Ihren spärlichen Fall angegeben. Beachten Sie auch, dass der oben erwähnte BFS-Ansatz sowohl für gerichtete als auch für ungerichtete Diagramme funktioniert.

Es gibt Johnsons Algorithmus , dessen Laufzeit .$O(V^2\log V + VE)$

Sie können versuchen, eine Version von Floyd-Warshall zu erstellen, die auf spärlichen Matrizen schneller ist.

Erinnern wir uns zunächst, was dieser Algorithmus bewirkt:

Sei eine Matrix von Entfernungen. Zu Beginn des Algorithmus M i ist j das Gewicht der Kante i → j . Wenn diese Kante nicht existiert, dann ist M i , j = ∞ .$M$$M_{i,j}$$i \rightarrow j$$M_{i,j}=\infty$

Der Algorithmus hat Schritte. In Schritt k des Algorithmus setzen wir für jedes Knotenpaar i , $V$$k$$i,j$

$$M_{i,j} \leftarrow \min\{M_{i,j}, M_{i,k}+M_{k,j}\}.$$

Es ist klar, dass keine Aktualisierung durchgeführt werden muss, wenn oder M k , j = ∞ ist. So wird in den ersten Schritten des Algorithmus, brauchen wir nur grob auszuführen d e g i n ( k ) ⋅ d e g o u t ( k ) Vergleiche , wo d e g i n ( k ) und d e g o u t$M_{i,k}=\infty$$M_{k,j}=\infty$$deg_{in}(k) \cdot deg_{out}(k)$$deg_{in}(k)$ bezeichnen die Anzahl der ankommenden und abgehenden Flanken des k- ten Knotens. Mit fortschreitendem Algorithmus werden immer mehr Einträge der Matrix M gefüllt. Daher können die letzten Schritte viel länger dauern.$deg_{out}(k)$$k$$M$

Beachten Sie, dass wir eine effiziente Methode benötigen, um nur nicht unendliche Zellen in der ten Zeile und Spalte der Matrix zu durchlaufen . Dies kann erreicht werden, indem für jeden Knoten eine Reihe von eingehenden und ausgehenden Kanten gespeichert wird.$k$

Es scheint, dass die ersten Schritte des Algorithmus stark von Sparsity profitieren können. Beispielsweise legt ein zufällig konstruierter Graph mit nahe, dass die erste Iteration ( k = 0 ) nur aus O ( 1 ) Schritten besteht. Wenn der Graph in viele verbundene Komponenten aufgeteilt wird, bleibt die Matrix M während des gesamten Algorithmus relativ dünn, und die Gesamtlaufzeit könnte so niedrig wie O ( V ) sein . Enthält der Graph dagegen nur eine zusammenhängende Komponente, so ist die letzte Iteration k = | V $E=O(V)$$k=0$$O(1)$$M$$O(V)$$k=|V|$Es wird erwartet, dass Schritte unternommen werden. In diesem Fall könnte die Gesamtlaufzeit O ( V 3 ) sein . So groß wie die nicht spärliche Version.$O(V^2)$$O(V^3)$