Algorithmus in Python (Dijkstra)

Einführung

Ich möchte den Inhalt der Bibliothek, die ich bisher nur eingefügt hatte, nach und nach studieren. Der Grund für das Schreiben dieses Artikels ist, dass ich meine Gedanken bestätigen und Ratschläge geben möchte. Bitte kommentieren Sie dies! (Insbesondere Beschleunigung, Berechnungsbetrag)

Zweck

Finden Sie den kürzesten Abstand von einem Startpunkt zum anderen für ein Diagramm ohne negative Kostenkanten. (Einzelstartpunkt kürzeste Route)

Prinzip

Stellen Sie sich den Fall vor, in dem die Anzahl der Eckpunkte im Diagramm $ V $ und die Anzahl der Seiten $ E $ beträgt. Bereiten Sie zunächst zwei Listen vor. Zum einen wird die kürzeste Entfernung vom Startpunkt aufgezeichnet, und zum anderen wird aufgezeichnet, ob die kürzeste Route ermittelt wurde. (Es scheint, dass es zu einem kombiniert werden kann, aber es ist dasselbe wie beim Verstehen.) Hier ist der Abstand zu Ihrem eigenen Punkt auf 0 festgelegt, und der Abstand zu anderen Punkten ist INF. Bereiten Sie eine priorisierte Warteschlange vor, um den Mindestwert für die Kosten der Kante abzurufen. Dann wird die Seite, die sich von ihrem eigenen Punkt aus erstreckt, in die Prioritätswarteschlange gestellt. Zu diesem Zeitpunkt ** ist das Ziel der Seite mit den Mindestkosten nicht geringer als die Kosten über andere Seiten **. Da die Kosten nicht negativ sind, wird es ein Umweg sein. Daher wird die Seite mit den minimalen Kosten herausgenommen und der kürzeste Abstand zum Scheitelpunkt dieses Ziels bestimmt. Darüber hinaus wird die Seite, die sich von diesem Scheitelpunkt aus erstreckt, auf die gleiche Weise in die Prioritätswarteschlange gestellt. Die Entfernung ist ** die Entfernung zu diesem Scheitelpunkt + die Kosten der Seite **. Da hier die Seite mit dem Ziel, für das die kürzeste Entfernung festgelegt ist, nicht mit der kürzesten Entfernung in Beziehung steht, wird der Rechenaufwand geringer, wenn er nicht enthalten ist. Wiederholen Sie den obigen Vorgang, bis alle kürzesten Entfernungen ermittelt sind. (In der Implementierung ist die Prioritätswarteschlange leer.)

Implementierung

import heapq
def dijkstra(s):
    #Der kürzeste Abstand vom Startpunkt zu jedem Scheitelpunkt
    d = [float('inf')]*n
    d[s] = 0
    #Ob jeder Scheitelpunkt besucht wurde
    used = [False]*n
    used[s] = True
    #Haufen, um temporäre Entfernung aufzuzeichnen
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        u, v = heapq.heappop(que)
        if used[v]:
            continue
        d[v] = u
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

Eingang

n = 4
g = [[[1, 1], [4, 2]], [[1, 0], [2, 2], [5, 3]], [[4, 0], [2, 1], [1, 3]], [[1, 2], [5, 1]]] #Benachbarte Liste
print(dijkstra(0))

Ausgabe

[0, 1, 3, 4]

Computergestützte Mengenanalyse

Das Hinzufügen zur Prioritätswarteschlange ist $ O (E) $, abhängig von der Anzahl der Seiten. Die Größe der Prioritätswarteschlange ist proportional zu $ V $, indem die Seiten nicht berücksichtigt werden, es sei denn, sie sind die kürzeste Entfernung, sodass jede Operation $ O (logV) $ ist. Daher beträgt der Berechnungsbetrag $ O (ElogV) $.

Frage

Ich fragte mich, ob die Größe der Prioritätswarteschlange proportional zur Anzahl der Seiten $ E $ war, aber ich zögerte ein wenig, sie im Verhältnis zu $ V $ zu beschneiden. Wenn Sie es konkret ausschreiben, können Sie sehen, dass es niemals $ E $ erreichen wird, aber ich würde gerne wissen, ob es leicht durch eine mathematische Formel ausgedrückt werden kann. Erstens, wenn die Seite zwischen allen Eckpunkten gespannt ist, wird sie zu $ E∝V ^ 2 $, was schlimmer ist als bei anderen $ O (V ^ 2) $ -Algorithmen, daher denke ich nicht, dass es notwendig ist, darüber nachzudenken!

Konkretes Beispiel

Das obige Beispiel. Wir werden diejenige mit den niedrigsten Kosten unter den erreichbaren Eckpunkten auswählen und aktualisieren.

abschließend

Ich möchte es weiterhin als Memorandum aktualisieren. Ich bin motivierter, weil die Artikel manchmal als Referenz verwendet werden.

Verweise

[Programmierwettbewerb-Herausforderungsbuch](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F% E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E3% 83% 81% E3% 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 83% 96% E3% 83% 83% E3% 82% AF-% E7% AC% AC2% E7% 89 % 88-% EF% BD% 9E% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E6% B1% BA% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% B4% BB% E7% 94% A8% E5% 8A% 9B% E3% 81% A8% E3% 82% B3% E3% 83% BC% E3% 83% 87% E3% 82% A3% E3% 83% B3% E3% 82% B0% E3% 83% 86% E3% 82% AF% E3% 83% 8B% E3% 83% 83% E3% 82% AF% E3% 82% 92% E9% 8D% 9B% E3% 81% 88% E3% 82% 8B% EF% BD% 9E-% E7% A7 % 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89-ebook / dp / B00CY9256C) [Juppys Blog](https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3 % 82% A4% E3% 82% AA% E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AD% E3% 83% A5% E3% 83% BC% 28heapq% 29 % E3% 82% 92% E7% 94% A8% E3% 81% 84% E3% 81% 9F% E3% 83% 97% E3% 83% AA% E3% 83% A0% E6% B3% 95)