Kürzeste Wege, die jede Kante verbieten

9

Ich würde mich über Hinweise oder Begriffe freuen, die mich in die richtige Richtung führen könnten.

Wir haben einen gerichteten Graphen und Längen für jede Kante , die als positiv angenommen werden können. Es gibt einen speziellen Startknoten und einen speziellen Endknoten . $G=(V,E)$ $l_{ij}$ $ij$ $s$ $t$

Für jede Kante möchten wir die Länge des kürzesten Pfades von nach berechnen , der keine Kante . $ij$ $s$ $t$ $ij$

Ein einfacher Brute-Force-Algorithmus besteht darin, für jede Kante einen Algorithmus mit dem kürzesten Pfad auszuführen, wobei jedes Mal eine andere Kante aus dem ursprünglichen Diagramm entfernt wird. Gibt es einen effizienteren Algorithmus, der die Tatsache ausnutzt, dass in diesem Brute-Force-Algorithmus viele wiederholte Berechnungen stattfinden?

Danke im Voraus.

ds.algorithms reference-request graph-algorithms dan_x
quelle

18

Das von Ihnen erwähnte Problem wird als "Ersatzpfade" bezeichnet. Hier einige Referenzen:

$O(mn+n^2\log\log n)$ $n$ $m$
A. Bernstein. Ein nahezu optimaler Algorithmus zur Approximation von Ersatzpfaden und k kürzesten einfachen Pfaden in allgemeinen Graphen. In Proc. SODA, Seiten 742–755, 2010. Dieses Papier gibt erstaunlicherweise ein quasilineares Zeitnäherungsschema für das Problem.
$\Omega(m\sqrt{n})$
$O(n^{3-\varepsilon})$ $\varepsilon>0$ $O(n^{3-\varepsilon'})$ $\varepsilon'>0$
$\{-M,\ldots, M\}$ $\tilde{O}(Mn^\omega)$

Jungfrau
quelle

8

$s$ $t$ $n-1$

Nathann Cohen
quelle

Vielen Dank. Ich habe die andere Antwort akzeptiert, weil sie mehr von dem Kontext enthält, nach dem ich gesucht habe, aber ich werde diesen Ansatz wahrscheinlich für die Implementierung des ersten Durchgangs verwenden, die ich benötige.

dan_x

Kürzeste Wege, die jede Kante verbieten

Antworten: