Linearer Zeitalgorithmus zum Finden von

Definition. Bei einem gegebenen Graphen und zwei Scheitelpunkte s und t , die k -shortest-Pfade Problem ist das Finden der k kürzesten einfache Wege zwischen s und t in G .$G=(V,E)$$s$$t$$k$$k$$s$$t$$G$

Es ist zu beachten, dass die Länge dieser Pfade nicht notwendigerweise gleich ist und die Eckpunkte und t notwendigerweise k- verbunden sind. Ich habe mich gefragt, ob es für dieses Problem einen linearen Zeitalgorithmus (in Bezug auf n und m ) gibt.$s$$t$$k$$n$$m$

Ich habe mir einige Artikel in der Literatur angesehen, wie zum Beispiel " Eine neue Implementierung von Yens Algorithmus für schleifenlose Pfade ", aber die zeitliche Komplexität ist wirklich hoch . In der anderen Veröffentlichung von Epstein " Finden der k kürzesten Pfade " wird ein Algorithmus vorgestellt, der die k kürzesten Pfade findet, die nicht unbedingt einfache Pfade mit der Laufzeit O ( n + m + k ) sind .$O(Kn(m+nlogn))$$k$$O(n+m+k)$

Gibt es einen linearen Zeitalgorithmus für das Problem der einfachen kürzesten Wege?$k$

Die Antwort, die hier gilt, wurde von Raphael bereits in den Kommentaren zu der Frage gegeben: " Da wir nicht einmal wissen, wie man einen einfachen kürzesten Weg in linearer Zeit findet, bezweifle ich dies. " Ich gehe daher davon aus, dass Sie daran interessiert sind, die besten verfügbaren Algorithmen nach dem aktuellen Stand der Technik zu kennen. Im Folgenden beschreibe ich die beste Worst-Case-Bindung (nach bestem Wissen), aber auch einen Algorithmus, der in bestimmten Fällen in linearer Zeit ausgeführt werden kann.

Bevor ich jedoch die neuesten Entwicklungen auf dem neuesten Stand der Technik beschrieb, wollte ich die Bedeutung einfacher Wege für dieses spezielle Problem hervorheben . Tatsächlich übersehen viele Menschen die Bedeutung dieser Anforderung und einige verstehen sie nicht einmal auf den ersten Blick.

Bei der Berechnung des kürzesten Pfades von einem Startscheitelpunkt zu einem Zielscheitelpunkt ist der optimale Pfad notwendigerweise einfach , dh er wiederholt keine Scheitelpunkte. Wenn jedoch optimale Pfade berechnet werden, sind die zweiten, dritten, ... besten Pfade möglicherweise nicht einfach. Um dies zu beweisen, stelle ich hier ein Beispiel zur Verfügung, das von Hershberger, Maxel & Suri, 2007, leicht angepasst wurde:$k$

$s$$t$$\pi_1 : \langle s, A, B, C, D, t\rangle$$\pi_2 : \langle s, A, B, C, D, C, D, t\rangle$$\pi_3 : \langle s, A, B, A, B, C, D, t\rangle$$\pi_2 : \langle s, F, t\rangle$$\pi_3 : \langle s, G, t\rangle$

$G(V, E)$$V$$\langle u, v\rangle\in E, u, v\in V$$u$$v$

$k$$O(|E|+|V|\log |V|+k)$$K^*$

$O(k|V|(|E|+|V|\log |V|))$$O(k(|E|+|V|\log |V|))$$k$

$k$

Hoffe das hilft,

Literaturverzeichnis

$K^*$$k$

$k$

$k$

$k$

$k$

$k$

$k$