Der aufeinanderfolgende Algorithmus für kürzeste Pfad (SSP) ist eine leistungsstarke Technik zur Lösung des Mindestkostenflussproblems in einem Netzwerk. Hier ist eine Aufschlüsselung des Prozesses, der an der Implementierung beteiligt ist:
1. Problemdefinition:
* Netzwerk: Sie arbeiten mit einem angegebenen Diagramm (Netzwerk), das dargestellt wird, das von:
* Knoten (Scheitelpunkte): `V` (z. B. Fabriken, Lagerhäuser, Städte)
* bögen (Kanten): `E` (z. B. Straßen, Pipelines, Kommunikationsverbindungen)
* Kapazitäten: Jedes Bogen `(u, v)` in `e` hat eine Kapazität` c (u, v) `, die den maximalen Fluss darstellt, der durch ihn gelangen kann.
* Kosten: Jedes Bogen `(u, v)` in `e` hat Kosten` Kosten (u, v), die die Kosten pro Flusseinheit durch diesen Bogen darstellen.
* Angebot/Nachfrage: Jeder Knoten `v` in` v` hat eine Versorgung `b (v)`.
* Wenn `b (v)> 0`, der Knoten` v` ist eine * Quelle * mit einer Versorgung mit `b (v)` Einheiten.
* Wenn `b (v) <0`, der Knoten` v` ist eine * Sink * mit einer Nachfrage von `-b (v)` Einheiten.
* Wenn `b (v) =0` ist, ist der Knoten` v` ein Umschlagknoten.
* Ziel: Ermitteln Sie die Durchflusszuordnung, die die Gesamtkosten für den Senden des Flusses durch das Netzwerk minimiert und gleichzeitig die Angebots-/Nachfrageinschränkungen und Kapazitätsbeschränkungen erfüllt.
2. Initialisierung:
* Restnetzwerk: Erstellen Sie ein Restnetzwerk `g_f` basierend auf dem ursprünglichen Netzwerk` g`. Anfangs ist `g_f =g`. Dieses Netzwerk verfolgt die verfügbare Kapazität. Für jeden Bogen `(u, v)` In `g` ist die Restkapazität` c_f (u, v) =c (u, v) - f (u, v) `, wobei` f (u, v) `der Stromfluss auf diesem Bogen ist. Anfangs ist `f (u, v) =0` für alle Bögen.
* Fluss: Initialisieren Sie den Fluss `f (u, v) =0` für alle Bögen im ursprünglichen Netzwerk.
* Potenziale (Preise): Initialisieren Sie eine potenzielle Funktion `pi (v)` für jeden Knoten `v` in` v`. Ein häufiger Ausgangspunkt ist `pi (v) =0` für alle` v`. Die Potentiale sind für den Umgang mit negativen Kostenzyklen von entscheidender Bedeutung.
3. Algorithmus Schritte:
Der Kern des aufeinanderfolgenden kürzesten Pfadalgorithmus ist ein iterativer Prozess:
A. Finden Sie eine Quelle und eine Spüle: Wählen Sie im Netzwerk einen Quellknoten `s` (wobei` b (s)> 0`) und ein Sinkknoten `t` (wobei` b (t) <0`) im Netzwerk. Wenn keine solchen Knoten existieren, ist der Algorithmus vollständig.
B. kürzeste Pfadberechnung: Finden Sie den kürzesten Pfad `p` von` s` zu `t` im *restlichen Netzwerk *` g_f` mit den *reduzierten Kosten *. Die reduzierten Kosten für einen Bogen `(u, v)` sind definiert als:
`` `
cost_reced (u, v) =cost (u, v) + pi (u) - pi (v)
`` `
* Das Ziel der Verwendung reduzierter Kosten ist es, negative Kostenzyklen zu beseitigen. Wenn die Potentiale `pi` so ausgewählt werden, dass` cost_reced (u, v)> =0` für alle Bögen, dann kann Dijkstras Algorithmus verwendet werden, um den kürzesten Weg zu finden.
* Wenn negative Kosten nach Anwendung von Potenzialen bestehen, kann der Bellman-Ford-Algorithmus verwendet werden (aber im Allgemeinen ist es langsamer).
C. Augment Flow: Sei `Delta` das Minimum von:
* `b (s)` (die verbleibende Versorgung bei Quelle `s`)
* `-b (t)` (die verbleibende Nachfrage bei Sink `t`)
* Die minimale Restkapazität entlang des kürzesten Pfades `p`:` min {c_f (u, v) | (u, v) in p} `
Aktualisieren Sie den Fluss entlang des Pfades `p` von` Delta`:
* Für jeden Bogen `(u, v)` in `p`:
* `f (u, v) =f (u, v) + Delta`
* Aktualisieren Sie die Restkapazität:`c_f (u, v) =c (u, v) - f (u, v)`
* Wenn im ursprünglichen Netzwerk `(u, v)` vorhanden ist, aktualisieren Sie seine umgekehrte Kante im Restnetzwerk:Erstellen Sie die Kante `(v, u)` in `g_f`, wenn es nicht mit` c_f (v, u) =f (u, v) `existiert.
D. Angebot und Nachfrage aktualisieren:
* `b (s) =b (s) - Delta`
* `b (t) =b (t) + delta`
e. Potentiale aktualisieren (Bellman-Ford-Variante): Dies ist ein * entscheidender * Schritt, um nicht negative reduzierte Kosten aufrechtzuerhalten und das korrekte Verhalten zu gewährleisten. Nach dem Austausch des Flusses müssen Sie die Potenziale aktualisieren. Ein gemeinsamer Ansatz (oft in Verbindung mit Dijkstra nach einem ersten Bellman-Ford) ist eine Bellman-Ford-Variante. Dies kann mit den kürzesten Pfadentfernungen aus der vorherigen Iteration erfolgen, jedoch auf alle Eckpunkte angewendet werden. Der Schlüssel besteht darin, sicherzustellen, dass alle durch die Durchflussvergrößerung eingeführten negativen Kostenzyklen behandelt werden.
* Option 1:Voller Bellman-Ford (weniger effizient): Bellman-Ford von einem willkürlichen Knoten `r` an alle anderen Knoten in` g_f` mit den reduzierten Kosten neu `r`. Sei `D (v)` der kürzeste Abstand von `r` zu` v`. Aktualisieren Sie die Potentiale:`pi (v) =pi (v) - d (v)`. Dies garantiert "cost_reced (u, v)> =0" für alle Bögen nach dem Update, ist jedoch relativ langsam.
* Option 2:Johnsons Algorithmus (effizient): Führen Sie Bellman-Ford einmal aus, um anfängliche Potentiale zu berechnen. Verwenden Sie anschließend den Algorithmus von Dijkstra mit den reduzierten Kosten. Nach jeder Augmentation werden die Potentiale mithilfe von Dijkstra Ergebnis neu berechnen.
F. Wiederholung: Gehen Sie zurück zu Schritt (a) und wiederholen Sie den Vorgang, bis alle Vorräte und Anforderungen erfüllt sind (`b (v) =0` für alle Knoten` v`).
4. Kündigung:
Der Algorithmus endet, wenn alle Vorräte und Anforderungen erfüllt sind. Der resultierende Fluss `f (u, v)` für alle Bögen `(u, v)` im ursprünglichen Netzwerk repräsentiert den Mindestkostenfluss.
Schlüsseldatenstrukturen:
* Adjazenzliste/Matrix: Um das Netzwerk `g` und das Restnetzwerk` g_f` darzustellen. Adjazenzlisten sind für spärliche Graphen in der Regel effizienter.
* Flussmatrix: Zum Speichern des Stromflusses `f (u, v)` auf jedem Bogen.
* Kapazitätsmatrix: Aufbewahrung der ursprünglichen Kapazitäten `C (u, v)` jedes Bogens.
* Restkapazitätsmatrix: Aufbewahrung der Restkapazitäten `c_f (u, v)` im Restnetzwerk.
* potenzielles Array: Zum Speichern der Potenziale `pi (v)` für jeden Knoten.
* Priority Queue (Heap): Wird im Dijkstra -Algorithmus zur effizienten kürzesten Pfadberechnung verwendet.
Code -Überlegungen (Python -Beispiel - vereinfacht):
`` `Python
Heapq importieren
Def Successive_shortest_path (Diagramm, Kapazität, Kosten, Versorgung):
"" "
Implementiert den aufeinanderfolgenden kürzesten Pfadalgorithmus.
Args:
Graph:Ein Wörterbuch, das die Grafik als Adjazenzliste darstellt.
Schlüssel sind Knoten, Werte sind Listen benachbarter Knoten.
Kapazität:Ein Wörterbuch, das die Kapazität jeder Kante darstellt (u, v).
Kosten:Ein Wörterbuch, das die Kosten jeder Kante darstellt (u, v).
Angebot:Ein Wörterbuch, das das Angebot/die Nachfrage jedes Knotens darstellt.
Positive Werte sind Angebot, negative Werte sind Nachfrage.
Rückgaben:
Ein Wörterbuch, das den Fluss an jeder Kante darstellt, oder keine, wenn keine realisierbare Lösung.
"" "
Flow ={} # Initialisieren Sie den Fluss auf Null
für u in Graph:
Für V in Graph [u]:
Fluss [(u, v)] =0
potential ={node:0 für node in graph} # potentiale initialisieren
während wahr:
Quellen =[Knoten für den Knoten in Versorgung, wenn Lieferung [Knoten]> 0]
Sinks =[Knoten für den Knoten in Versorgung, wenn Versorgung [Knoten] <0]
Wenn nicht Quellen oder nicht sinkt:
Break # Alle Angebot/Nachfrage zufrieden
Quelle =Quellen [0]
Sink =Sinks [0]
# Kürzester Pfad mit Dijkstra mit reduzierten Kosten
dist, prev =dijkstra (Diagramm, Kapazität, Kosten, Potenzial, Quelle, Waschbecken, Fluss)
Wenn dist [Sink] ==Float ('Inf'):# kein Weg gefunden, unmöglich vorhanden
Gibt keine # zurück oder verarbeiten Sie diesen Fall anders
# Augment Flow
Delta =min (Versorgung [Quelle], -Supply [Sink])
Curr =Sink
während Curr! =Quelle:
prev_node =prev [Curr]
Delta =min (Delta, Kapazität [(prev_node, curr)] - fließen [(prev_node, curr)])
Curr =prev_node
Curr =Sink
während Curr! =Quelle:
prev_node =prev [Curr]
Fluss [(prev_node, curr)] +=Delta
if (Curr, prev_node) in Kapazität:
Fluss [(Curr, prev_node)] -=Delta # Rückwärtsfluss
anders:
Flow [(Curr, prev_node)] =-delta # initialise bei Bedarf.
Curr =prev_node
Lieferung [Quelle] -=Delta
Lieferung [Sink] +=Delta
# Potentiale mit den Entfernungen von Dijkstra aktualisieren
Für den Knoten in Diagramm:
Potential [Knoten] +=dist [Knoten]
Rückfluss
Def Dijkstra (Graph, Kapazität, Kosten, Potenzial, Quelle, Waschbecken, Fluss):
"" "
Dijkstra -Algorithmus mit reduzierten Kosten.
"" "
dist ={node:float ('inf') für Knoten in Graph}
prev ={node:Keine für Knoten in Graph}
Dist [Quelle] =0
PQ =[(0, Quelle)] # Prioritätswarteschlange (Entfernung, Knoten)
Während PQ:
D, u =heapq.heapop (pq)
Wenn d> dist [u]:# faule Löschung
weitermachen
Für V in Graph [u]:
# Betrachten Sie nur Kanten mit Restkapazität> 0
Wenn Kapazität [(u, v)] - Fluss [(u, v)]> 0:
record_cost =cost [(u, v)] + potential [u] - potenziell [v]
Wenn dist [v]> dist [u] + reced_cost:
dist [v] =dist [u] + reced_cost
prec [v] =u
Heapq.Heappush (PQ, (dist [v], v))
return dist, prev
Beispiel Verwendung:
Graph ={
's':['a', 'b'],
'a':['b', 't'],
'B':['T'],
'T':[]
}
Kapazität ={
('s', 'a'):10,
('s', 'b'):5,
('a', 'b'):4,
('a', 't'):8,
('B', 'T'):12
}
kostete ={
('s', 'a'):2,
('s', 'b'):4,
('a', 'b'):1,,
('a', 't'):7,
('B', 'T'):5
}
Supply ={
's':15,
'a':0,,
'B':0,,
'T':-15
}
Flow =Suctive_shortest_path (Diagramm, Kapazität, Kosten, Versorgung)
Wenn Fluss:
print ("Flusszuweisung:", Flow)
# Die Gesamtkosten berechnen
Total_cost =sum (Flow [(u, v)] * Kosten [(u, v)] für (u, v) im Fluss)
print ("Gesamtkosten:", Total_Cost)
anders:
print ("Keine praktikable Lösung gefunden.")
`` `
Wichtige Überlegungen:
* Negative Kostenzyklen: Der SSP -Algorithmus ist so ausgelegt, dass sie negative Kostenzyklen bearbeiten. Die potenzielle Funktion `pi (v)` ist dafür von entscheidender Bedeutung. Wenn Sie die Potenziale nicht richtig aktualisieren, konvergieren der Algorithmus möglicherweise nicht oder erzeugt eine falsche Lösung.
* Dijkstra gegen Bellman-Ford:
* Wenn Sie * immer * nicht negative reduzierte Kosten aufrechterhalten, ist Dijkstra's Algorithmus viel schneller, um kürzeste Wege zu finden. Dies ist das ideale Szenario und wird normalerweise mit geeigneten potenziellen Aktualisierungen erreicht.
* Wenn Sie nicht negative reduzierte Kosten garantieren können, müssen Sie * Bellman-Ford verwenden, was langsamer ist (o (v * e) Zeitkomplexität). Es wird oft nur für die anfängliche potenzielle Berechnung verwendet.
* Restnetzwerk: Das korrekte Aufrechterhaltung des Restnetzes ist unerlässlich. Denken Sie daran, Hinterkanten zu erstellen, wenn der Fluss entlang eines Bogens gedrückt wird.
* Computerkomplexität: Die Komplexität des SSP -Algorithmus hängt vom kürzesten Pfadalgorithmus und der Anzahl der Iterationen ab. Im schlimmsten Fall kann es pseudopolynomisch sein, wenn die Kapazitäten groß sind.
* Alternative Algorithmen: Bei großen Problemen mit Mindestkostenfluss sind andere Algorithmen wie der Netzwerk-Simplex-Algorithmus häufig effizienter.
Zusammenfassend ist der aufeinanderfolgende kürzeste Pfadalgorithmus eine leistungsstarke und konzeptionell klare Methode zur Lösung minimaler Kostenflussprobleme. Das Verständnis der Rollen des Restnetzes, reduzierten Kosten und potenziellen Funktionen ist der Schlüssel zur korrekten Implementierung. Wählen Sie den entsprechenden kürzesten Pfadalgorithmus (Dijkstra oder Bellman-Ford), basierend darauf, ob Sie nicht negative reduzierte Kosten garantieren können. Denken Sie daran, die Updates in Angebot und Nachfrage zu bewältigen und die Potenziale korrekt zu aktualisieren.
