Zweck

Finden Sie den kürzesten Abstand von einem Scheitelpunkt zum anderen. (Kürzeste Route von einem einzelnen Startpunkt) ** Kann verwendet werden, auch wenn es eine Seite mit negativen Kosten gibt **.

Prinzip

Sei $ V $ die Anzahl der Eckpunkte und $ E $ die Anzahl der Seiten des Graphen. Erstellen Sie eine Liste $ d $, in der die Mindestkosten für jeden Scheitelpunkt aufgezeichnet werden. Hier ist der Abstand zum eigenen Punkt auf 0 festgelegt, und der Abstand zu anderen Punkten ist INF. Schauen Sie sich von hier aus alle Seiten an und aktualisieren Sie die kürzeste Entfernung. Insbesondere wenn die Seite $ e $ Informationen hat, die $ kosten, kostet $ vom Scheitelpunkt $ von $ zum Scheitelpunkt $ bis , $d[from] + cost < d[to]$$ Wenn der Wert von $ d [bis] $ auf $ d [von] + Kosten $ aktualisiert wird. Ein Gesamtbetrag von $ V -1 $, um alle Seiten zu betrachten, bestimmt alle Mindestkosten, wenn keine negativen Schließungen vorliegen. Mit anderen Worten, wenn die Mindestkosten zum $ V $ -ten Zeitpunkt noch aktualisiert werden, hat dies einen negativen Abschluss, sodass die korrekten Mindestkosten nicht erhalten werden können. Warum ist es also in Ordnung, die Operation in einer $ V -1 $ -Schleife abzuschließen? Erklären Sie, wie Sie sich selbst verstehen können. Derselbe Scheitelpunkt wird niemals in den kostengünstigsten Pfad zu einem Scheitelpunkt aufgenommen. Wenn es enthalten ist, gibt es eine negative geschlossene Route, sodass die richtige Route überhaupt nicht gefunden werden kann. Aus dem oben Gesagten ergibt sich die maximale Anzahl von Seiten, die im kürzesten Pfad zu einem bestimmten Scheitelpunkt enthalten sind, $ V -1 $. Wie Sie sehen können, indem Sie den Code danach überprüfen, ist die Reihenfolge der Seiten die Eingabereihenfolge. (Es wird nicht in der Reihenfolge der Nähe wie bei der Suche nach Breitenpriorität gesucht.) Mit anderen Worten, betrachten Sie den Prozess des Findens der kürzesten Route von $ V -1 $. Hoffentlich folgt eine Schleife den Kanten in der Reihenfolge von vorne, und diese kürzeste Route kann gefunden werden. Angenommen, die Reihenfolge der zu untersuchenden Seiten ist von hinten ordentlich angeordnet. Wenn zu diesem Zeitpunkt die Vorderseite nicht untersucht wird, kann die nachfolgende Seite nicht als Teil der kürzesten Route betrachtet werden. (Da der Abstand zu $ von $ nicht INF oder Mindestkosten beträgt) Mit anderen Worten, in diesem Fall kann nur eine der kürzesten Routen für jede Schleife gefunden werden. Dies ist also der schlimmste Fall und erfordert $ V -1 $ Schleifen.

In diesem Fall habe ich es mit der Absicht implementiert, in der Reihenfolge der Nähe in Bezug auf die Suche nach Breitenpriorität zu suchen. Wenn jedoch ein negativer geschlossener Pfad vorhanden ist, wird der Wert weiterhin auf unbestimmte Zeit aktualisiert, sodass ich der Ansicht war, dass dies erforderlich ist. Als es nur positive Kosten waren, warf ich es in das Problem von Aizu Online's Dyxtra und es war die richtige Antwort, also frage ich mich, ob es auch einen Namen hat.

Berechnungsanalyse

Im schlimmsten Fall wird die Operation zum Anzeigen aller Seiten $ V -1 $ Mal ausgeführt, sodass der Berechnungsbetrag $ O (EV) $ beträgt.

Implementierung

# O(EV)
def bellman_ford(s):
    d = [float('inf')]*n #Mindestkosten für jeden Scheitelpunkt
    d[s] = 0 #Entfernung zu sich selbst ist 0
    for i in range(n):
        update = False #Wurde das Update durchgeführt?
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        #Es gibt eine negative gesperrte Straße
        if i == n - 1:
            return -1
    return d

n, w = [int(x) for x in input().split()] # n:Anzahl der Eckpunkte, w:Anzahl der Seiten
g = []
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] #Startpunkt,Endpunkt,Kosten
    g.append([x, y, z])
    g.append([y, x, z]) #In gerichteter Grafik gelöscht
print(bellman_ford(0))

abschließend

In Bezug auf den Code bin ich diesmal ziemlich besorgt über die Denkweise. Bitte geben Sie an, wenn Sie möchten!

Verweise

Programmierwettbewerbs-Herausforderungsbuch