[PYTHON] Vollständiges Verständnis der Konzepte von Bellmanford und Dyxtra

Überblick

Wir haben die Dijkstra-Methode und die Bellman-Ford-Methode in einer internen Studiensitzung vorgestellt. Zu dieser Zeit habe ich verschiedene Beweise für den Algorithmus recherchiert, aber ich habe festgestellt, dass nicht viele Artikel erklärt wurden. Ich persönlich denke, dass die Frage "Warum passiert das?" Ein wichtiger Faktor ist, deshalb möchte ich diese Algorithmen in diesem Sinne einführen.

Was für eine Person ist der Schriftsteller?

Programmierhistorie: 1 Jahr (nur Python) Atcoder Tee Ich arbeite seit April 2020 für eine Datenanalyse-Sendungsfirma, aber aus irgendeinem Grund studiere ich nur Algorithmen.

Wann verwenden Sie diesen Algorithmus?

Es wird verwendet, um das Problem des kürzesten Wegs eines einzelnen Startpunkts eines gewichteten Graphen zu lösen.

Für jeden Begriff Gewichtet: Kosten für den Durchgang durch die Seite Einzelner Startpunkt: ein Startpunkt Kürzeste Route: Die Route vom Startpunkt zum Ziel zu den niedrigsten Kosten ist.

Nehmen Sie die folgende Grafik als Beispiel Ziel ist es, den kürzesten Weg vom Startpunkt $ A $ zu allen Seiten zu finden. Der kürzeste Weg von $ A nach E $ ist übrigens （A→D→B→F→E） ist. Wir werden dies unter Verwendung eines Algorithmus finden.

Vor dem Algorithmus die wichtigen Eigenschaften des Graphen

1. Die kürzeste Teilstraße ist die kürzeste Straße

Die Teilstraße der kürzesten Straße ist überall die kürzeste Straße.

Beweis
In der obigen Grafik vorübergehend der kürzeste Weg von $ A nach E $ （A→B→C→D→E　cost:5） Wird besorgt.

Davon kosten $ (A → B → C: 3) $ Ist eine Teilstraße dieser kürzesten Straße, aber wenn Sie den Scheitelpunkt B'für diesen Abschnitt verwenden Sie können die Kosten um eins weniger verschieben. Dann ist der kürzeste Weg in diesem Abschnitt （A→B'→C　cost:2） Daher $ A → E $ （A→B'→C→D→E　cost:4） Es kann mit bewegt werden, was der Annahme widerspricht. Die Teilstraße der kürzesten Straße ist immer die kürzeste Straße.

2. Pfadentspannung

Wenn Sie den kürzesten Pfad in der Reihenfolge der Eckpunkte finden, die sich auf den Startpunkt beziehen, werden schließlich alle kürzesten Pfade gefunden. Dies liegt daran, dass der kürzeste Weg, der allmählich vom Startpunkt aus erhalten wird, zu einem Teilweg des Scheitelpunkts wird, der über diesen Punkt hinausreicht.

Was ist die Bellmanford-Methode?

Finden Sie den kürzesten Weg zwischen allen Eckpunkten. Der Hauptunterschied zur Dyxtra-Methode besteht darin, dass ** negative Gewichte zulässig sind **.

Der Prozess der Suche nach dem kürzesten Weg ist

1. Konzentrieren Sie sich auf alle Seiten und aktualisieren Sie den Wert **, wenn Sie die Kosten für die Scheitelpunkte reduzieren können, die durch diese Seiten verlaufen **
2. Führen Sie den Vorgang 1. ** (Anzahl der Eckpunkte-1) mal ** durch ist.

In der folgenden Abbildung

In Prozess 1 können Sie $ A $ starten und $ C $ zu einem Preis von $ 5 $ erreichen. Notieren Sie sich dies also als $ C: 5 $. Als nächstes kann $ A → B $ bei $ -1 $ erreicht werden, so dass $ B: -1 $ und $ B → C $ zu einem Preis von $ -1 + 2 = 1 $ erreicht werden können. Zu diesem Zeitpunkt stellte ich fest, dass ich C zu einem geringeren Preis über $ B $ erreichen konnte, daher werde ich es auf $ C: 1 $ aktualisieren. Tun Sie dies für alle Seiten. Das ist das erste Mal. Wenn Sie danach (Anzahl der Scheitelpunkte 1) wiederholen, können Sie bei $ A $ beginnen und den kürzesten Weg zu allen Scheitelpunkten finden.

Warum machst du es (Anzahl der Eckpunkte-1) mal?

Die maximale Anzahl von Scheitelpunkten, die vom Startpunkt zum Ziel verlaufen, sind die Scheitelpunkte ohne den Startpunkt, dh (Anzahl der Scheitelpunkte-1). In dem oben beschriebenen Prozess wird immer der kürzeste Pfad (der Scheitelpunkt, der vom Startpunkt in der ersten Schleife verschoben werden kann) gefunden. In der zweiten Schleife wird ** immer ** der kürzeste Pfad gefunden (der Scheitelpunkt, der von der beim ersten Mal bestimmten Route verschoben werden kann). ・ ・ ・ Schließlich ist diese Schleife die Aufgabe, die kürzeste Route in der Reihenfolge vom Startpunkt aus zu finden, sodass es möglich ist, die kürzeste Route durch Routenentspannung zu finden.

Wenn Sie aufgrund eines negativen Gewichts in Schwierigkeiten sind

Siehe die Abbildung unten. Der eingekreiste Teil ist ein Zyklus, aber wenn Sie hier herumgehen, verringern sich die Kosten um -2. Mit anderen Worten, wenn Sie diesen Zyklus verwenden, können Sie die Kosten unendlich reduzieren. Dies wird als ** negativer Verschluss ** bezeichnet.

Die Bellmanford-Methode kann auch negative gesperrte Straßen erkennen. Früher habe ich bestätigt, dass der kürzeste Pfad in einer Schleife von (Anzahl der Eckpunkte-1) Mal gefunden wurde, aber die Kosten aller Eckpunkte werden erneut berechnet, und wenn es einen Eckpunkt gibt, der die Kosten aktualisieren kann, gibt es einen negativen geschlossenen Pfad. Wird sein.

Zeigen Sie mir den Quellcode

Es unterstützt die Eingabe des Adjazenzlistenformats (es gibt auch eine Adjazenzmatrix, die häufig bei Wettkampfprofis verwendet wird) und erkennt den kürzesten Weg nach der Bellmanford-Methode. Hier ist eine Beispieleingabe mit einem negativen Abschluss unterhalb des Codes (Grafik in der Abbildung oben). Ersetzt die Kosten der Eckpunkte durch den negativen Abschluss durch $ -inf $.

def shortest_path(s,n,es):
    #Kürzeste Entfernung von s → i
    # s:Startpunkt, n:Anzahl der Eckpunkte, es[i]: [辺のStartpunkt,Ende der Seite,Nebenkosten]
    
    #Gewichtsinitialisierung. Notieren Sie sich hier die kürzeste Entfernung
    d = [float("inf")] * n
    
    #Der Startpunkt ist 0
    d[s] = 0

    #Berechnen Sie die kürzeste Route
    for _ in range(n-1):
        # es:Über Seite i[from,to,cost]
        for p,q,r in es:
            #Aktualisiert, wenn die Wurzel des Pfeils durchsucht wurde und eine kostengünstige Route vorhanden ist
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
    
    #Überprüfen Sie die negative gesperrte Straße
    for _ in range(n-1):
        # e:Über Seite i[from,to,cost]
        for p,q,r in es:
            #Weil der zu aktualisierende Punkt vom negativen Abschluss betroffen ist-setze inf
            if d[q] > d[p] + r:
                d[q] = -float("inf")
    return d
################
#Eingang
n,w = map(int,input().split()) #n:Anzahl der Eckpunkte w:Anzahl der Seiten

es = [] #es[i]: [Der Ausgangspunkt der Seite,Ende der Seite,Nebenkosten]
for _ in range(w):
    x,y,z = map(int,input().split())
    es.append([x,y,z])
    # es.append([y,x,z])

print(shortest_path(0,n,es))

'''
Eingang
7 12
0 1 2 
0 2 -5
0 3 5
1 2 3
1 4 1
1 5 3
2 4 6
3 2 -2
3 5 4
4 6 -5
5 4 -2
6 2 -3
'''
>>[0, 2, -inf, 5, -inf, 5, -inf]

Der Berechnungsbetrag beträgt $ O (V ^ 2 + E) $ (Anzahl der Eckpunkte: $ V $, Anzahl der Seiten: $ E $).

Was ist die Dyxtra-Methode?

Es kann in Diagrammen mit nicht negativen Gewichten verwendet werden.

Das Finden des kürzesten Weges ist [Yobinoris Video]( ) Ist so leicht zu verstehen, dass es stirbt. (Yobinoris Verteidigungsbereich ist zu groß ...)

Ich werde es auch hier erklären.

Die Kosten des Scheitelpunkts seien (Anfangswert: $ S = 0 $, andere $ = ∞ $).

1. Beginnen Sie am kostengünstigsten Scheitelpunkt. Anfangs ist $ S $ der Ausgangspunkt.

2. Bestimmen Sie die Kosten des Startpunkts (grün in der Abbildung). Die Kosten für diesen Scheitelpunkt werden nicht mehr aktualisiert.

3. Notieren Sie sich die Startpunktkosten + Seitengewichte an den Eckpunkten, die vom Startpunkt aus verschoben werden können. Noted $ 7, 3, 1 $ am oberen Rand der mittleren Reihe. Die Kosten sind ungewiss, da sie möglicherweise noch aktualisiert werden.

4. Wiederholen Sie die Schritte 1 bis 3, bis alle Scheitelpunkte bestätigt sind. Von den angegebenen Scheitelpunkten ist der mit den Kosten von 1 der kleinste. Bestätigen Sie ihn also und notieren Sie die Scheitelpunkte, die von diesem Scheitelpunkt verschoben werden können. Wenn Sie zu geringeren Kosten umziehen können, aktualisieren Sie die Kosten.

Warum ist der kürzeste Weg erforderlich?

** Derjenige mit den niedrigsten Kosten unter den unbestimmten Eckpunkten kann nicht auf einen geringeren Preis aktualisiert werden **. Da es nur nicht negative Gewichte gibt, selbst wenn Sie eine andere Route wählen, betragen die Kosten 0 oder mehr. Daher können von den Unbestimmten die kleinsten Kosten als der kürzeste Weg bestimmt werden.

Wie lautet der Quellcode?

import heapq

def dijkstra(s, n, es):
    #Kürzester Abstand vom Startpunkt s zu jedem Scheitelpunkt
    #n:Anzahl der Eckpunkte, cost[u][v] :Seite UV-Kosten(Inf wenn es nicht existiert)
    d = [float("inf")] * n
    #Suchliste
    S = [s]
    #Prioritätswarteschlangen reduzieren den Rechenaufwand
    heapq.heapify(S)

    d[s] = 0
    
    while S:
        #Extrahieren Sie die Spitze der niedrigsten Kosten
        v = heapq.heappop(S)
        # print("-----------v", v)
        for u, w in es[v]:
            # print(u, w)
            #Aktualisieren Sie, wenn dies zu geringeren Kosten erreichbar ist, und fügen Sie es der Liste hinzu
            if d[u] > d[v]+w:
                d[u] = d[v]+w
                heapq.heappush(S, u)
        # print("d", d)
    return d

n,w = map(int,input().split()) #n:Anzahl der Eckpunkte w:Anzahl der Seiten

cost = [[float("inf") for i in range(n)] for i in range(n)] 
es = [[] for _ in range(n)]

for i in range(w):
    x, y, z = map(int, input().split())
    es[x].append([y, z])
    es[y].append([x, z]) #Löschen Sie diese Zeile für gerichtete Diagramme
# print(es)
print(dijkstra(0, n, es))

Referenzen oder Websites

・ Einführung in den Algorithmus 3. Ausgabe Band 2: Fortgeschrittene Entwurfs- und Analysemethode ・ Fortgeschrittene Datenstruktur ・ Graph-Algorithmus (Weltstandard-MIT-Lehrbuch) (T. Colmen, R. Rivest, C. Stein, C. Riserson, Tetsuo Asano, Kazuo Iwano, Hiroshi Umeo, Masashi Yamashita, Koichi Wada) Es ist ein ziemlich schweres Buch, aber der Beweis der Graphentheorie war sehr höflich.

・ Graphentheorie ⑤ (Dixtra-Algorithmus) ("Universitätsmathematik und Physik" an der Vorbereitungsschule gelernt) https://www.youtube.com/watch?v=X1AsMlJdiok Sie können die Dyxtra-Methode vollständig verstehen, indem Sie sich dieses Video ansehen!

・ Arimoto Python Single Shortest Route Methode 2 (Dyxtra-Methode) Wettbewerbsprogrammierung (Juppys Blog und Code sind hier.) https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%8D%98%E4%B8%80%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%952%EF%BC%88%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95%EF%BC%89_%E7%AB%B6%E6%8A%80%E3%83%97

Bonus

Das Diagramm im Artikel wurde mit networkx gezeichnet. Ich werde den Code für diejenigen setzen, die sich interessieren.

#Dikstra-Methodendiagramm
import matplotlib.pyplot as plt
import networkx as nx

#Satz gerichteter Graphen
G = nx.DiGraph()

#Kanten hinzufügen
# G.add_edges_from([("A", "B", {"weight":2)])
# nx.add_path(G, ["A", "C"])
# G.edges["A", "B"]["weight"] = 2
G.add_weighted_edges_from([("A", "B", 5), ("A", "C", 7), ("A", "D", 1), ("B", "C", 3), ("B", "F", 3), ("D", "B", 2)])
G.add_weighted_edges_from([("C", "E", 3), ("D", "F", 8), ("F", "E", 2), ("B", "E", 6)])

#Wenn Sie die Koordinaten der Scheitelpunkte in der Abbildung nicht angeben, werden sie zufällig angeordnet.
pos1 = {}
pos1["A"] = (0, 0)
pos1["B"] = (1, 0)
pos1["C"] = (1, 2)
pos1["D"] = (1, -2)
pos1["E"] = (2, 1)
pos1["F"] = (2, -1)

#Wenn Sie es so zeichnen, wie es ist, ist das Gewichtscharakter ein Hindernis. Löschen Sie es also
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}

#Schreiben Sie Gewicht
nx.draw_networkx_edge_labels(G, pos1, edge_labels=edge_labels, font_size=18)
#Zeichnung
nx.draw_networkx(G, pos1, node_size=1000, label_pos=100, node_color="r", font_size=18)
#Abbildung speichern
plt.savefig("dijkstra.png ")
plt.show()

#Die Dyxtra-Methode ist auch in networkx implementiert. Der Berechnungsbetrag beträgt O.(V^2+E)So langsam
pred, dist = nx.dijkstra_predecessor_and_distance(G, "A")
print(pred, dist)

>>{'A': [], 'B': ['D'], 'C': ['B'], 'D': ['A'], 'F': ['B'], 'E': ['F']} 
>>{'A': 0, 'D': 1, 'B': 3, 'C': 6, 'F': 6, 'E': 8}