Modifizieren des Dijkstra-Algorithmus für Kantengewichte aus dem Bereich

10

Angenommen, ich habe einen gerichteten Graphen mit Kantengewichten aus dem Bereich in dem K konstant ist. Wie kann ich den Algorithmus / die Datenstruktur ändern und die zeitliche Komplexität auf O ( | V | + | E | ) verbessern, wenn ich versuche, den kürzesten Weg mithilfe des Dijkstra-Algorithmus zu finden ?[1,,K]KO(|V|+|E|)

user1675999
quelle
Sie sollten genauer sagen: Was ist Ihre Datenstruktur? Und Sie können nicht weniger . Vorlesungen überprüfen. O(V+E)
Jonaprieto
Nur weil die Möglichkeiten für unterschiedliche Kantengewichte gering sind, bedeutet dies nicht, dass die Anzahl der Abstände gering ist.
Joe
3
Färben Sie zuerst die Scheitelpunkte Ihres Diagramms mit Blau, unterteilen Sie dann jede Kante der Größe in t Kanten (indem Sie t - 1 ungefärbte Scheitelpunkte hinzufügen ), und führen Sie dann das BFS für dieses neue Diagramm aus, um die kürzesten Pfade vom Startknoten zu den blauen Knoten zu finden O ( | V | + | E | ), wenn Sie die Konstante k haben . ttt1O(|V|+|E|)k
@SaeedAmiri warum nicht als Antwort aufschreiben?
Joe
@ Joe, weil es dijkstra nicht ändert (zumindest direkt nicht mit dijkstra verwandt).

Antworten:

16

Wenn Kantengewichte Ganzzahlen in , können Sie Dijkstra so implementieren, dass sie in O ( K | V | + | E | ) Zeit ausgeführt werden, gemäß dem Vorschlag von @ rrenaud. Hier ist eine explizitere Erklärung.{0,1,,K}O(K|V|+|E|)

Zu jedem Zeitpunkt befinden sich die (endlichen) Schlüssel in der Prioritätswarteschlange in einem Bereich , wobei D der Wert des letzten aus der Prioritätswarteschlange entfernten Schlüssels ist. (Jeder Schlüssel ist mindestens D , da die durch den Dijkstra-Algorithmus entfernte Tastenfolge nicht abnimmt und jeder Schlüssel höchstens D + K ist , da jeder Schlüssel den Wert d [ u ] + w t ( u , w ) für hat eine Kante ( u ,{D,D+1,,D+K}DDD+Kd[u]+wt(u,w) wobei d [ u ] der Abstand von der Quelle zu einembereits entferntenScheitelpunkt u ist, also d [ u ] D. )(u,w)d[u]ud[u]D

Aus diesem Grund können Sie die Prioritätswarteschlange mit einem kreisförmigen Array der Größe K + 1 implementieren , wobei jede Zelle einen Bucket enthält. Speichern Sie jeden Scheitelpunkt mit dem Schlüssel k im Bucket in Zelle A [ h ( k ) ], wobei h ( k ) = k mod ( K + 1 ) . Behalten Sie den Überblick von D . Führen Sie die folgenden Schritte aus:A[0..K]K+1kA[h(k)]h(k)=kmod(K+1)D

  • delete-min : Während ist leer, Inkrement D . Löschen Sie dann einen Scheitelpunkt aus A [ h ( D ) ] und geben Sie ihn zurück .A[h(D)]DA[h(D)]

  • Einfügen mit Schlüssel : Fügen Sie den Scheitelpunkt zum Eimer von A [ h ( k ) ] hinzu .kA[h(k)]

  • Verkleinerungsschlüssel auf k ' : Verschieben Sie den Scheitelpunkt von A [ h ( k ) ] nach A [ h ( k ' ) ] .kkA[h(k)]A[h(k)]

Einfügen und Verringern sind Operationen mit konstanter Zeit, daher beträgt die Gesamtzeit, die für diese Operationen aufgewendet wird, . Die Gesamtzeit im Lösch-min wird O ( | V | ) und der Endwert D . Der Endwert von D ist der maximale (endliche) Abstand von der Quelle zu einem beliebigen Scheitelpunkt (weil eine Löschmin, die i Iterationen benötigt, D um i erhöht ). Der maximale Abstand beträgt höchstens K ( | V | - 1O(|V|+|E|)O(|V|)DDiDi weil jeder Pfad höchstens | hat V | - 1 Kanten. Somit beträgt die Gesamtzeit, die der Algorithmus benötigt, O ( K | V | + | E | ) .K(|V|1)|V|1O(K|V|+|E|)

Neal Young
quelle
Ich mag die kreisförmige Warteschlange, das ist viel besser als meine Vorstellung, im Grunde genommen ein Array mit K * v-Größe zu haben, in dem zu einem bestimmten Zeitpunkt nur ein Slice mit Av-Größe verwendet wird.
Rrenaud
Ich habe es mithilfe einer doppelt verknüpften Liste implementiert. Bedeutet das immer noch, dass es O (1) ist, um den Min-Schlüssel zu finden?
user1675999
@ user1675999, ich bin nicht sicher. Wenn Ihre Liste nach Schlüsseln sortiert ist, wie können Sie Schlüssel effizient einfügen und verringern? Wenn Ihre Liste nicht nach Schlüsseln sortiert ist, wie können Sie Min effizient löschen?
Neal Young
5

Ich gehe hier davon aus, dass eine ganze Zahl ist und die Kantengewichte ganzzahlig sind. Andernfalls kauft es Ihnen nicht wirklich etwas. Sie können Gewichte immer neu skalieren, sodass die minimale Kante 1 und die maximale Kante K gekostet hat. Das Problem ist also identisch mit dem Standardproblem des kürzesten Pfades.K1K

K×|V|KK×|V|K×|V|=O(|V|)

rrenaud
quelle
-2

Sie können die topologische Sortierung verwenden, um die Lösung zu finden. Lassen Sie die Quelle den Grad 0 haben. Gehen Sie dann von jeder Kante zur Quelle. Wenn ein anderer Scheitelpunkt den Grad 0 hat, stellen Sie ihn in die Warteschlange und fahren Sie damit fort. In diesem Fall (ohne Zyklus innerhalb des Graphen) kann V + E erreicht werden, da es jeden Scheitelpunkt und jede Kante einmal und nur einmal durchlaufen würde.

TIANYANG ZHANG
quelle
Scheint nichts mit der Frage zu tun zu haben? Bei der Frage wird nicht davon ausgegangen, dass der Graph azyklisch ist, und Ihre Lösung nutzt nicht die Tatsache, dass Gewichte aus einem konstanten Bereich gezogen werden.
xskxzr