1. Probleemdefinitie:

* Netwerk: U werkt met een gerichte graaf (netwerk), weergegeven door:

* Knooppunten (hoekpunten): `V` (bijvoorbeeld fabrieken, pakhuizen, steden)

* Bogen (randen): 'E' (bijvoorbeeld wegen, pijpleidingen, communicatieverbindingen)

* Capaciteiten: Elke boog `(u, v)` in `E` heeft een capaciteit `c(u, v)` die de maximale stroom vertegenwoordigt die er doorheen kan gaan.

* Kosten: Elke boog `(u, v)` in `E` heeft kosten `cost(u, v)` die de kosten per stroomeenheid door die boog vertegenwoordigen.

* Aanbod/vraag: Elk knooppunt `v` in `V` heeft een voorraad `b(v)`.

* Als `b(v)> 0`, is knooppunt `v` een *bron* met een aanbod van `b(v)`-eenheden.

* Als `b(v) <0`, is knooppunt `v` een *sink* met een vraag naar `-b(v)` eenheden.

* Als `b(v) =0`, is knooppunt `v` een overslagknooppunt.

* Doelstelling: Zoek de stroomtoewijzing die de totale kosten van het verzenden van stroom door het netwerk minimaliseert en tegelijkertijd voldoet aan de beperkingen van vraag en aanbod en capaciteitsbeperkingen.

2. Initialisatie:

* Residueel netwerk: Creëer een restnetwerk `G_f` gebaseerd op het originele netwerk `G`. Initieel is `G_f =G`. Dit netwerk houdt de beschikbare capaciteit bij. Voor elke boog `(u, v)` in `G` is de restcapaciteit `c_f(u, v) =c(u, v) - f(u, v)`, waarbij `f(u, v)` de stroom op die boog is. Aanvankelijk is `f(u, v) =0` voor alle bogen.

* Stroom: Initialiseer de stroom `f(u, v) =0` voor alle bogen in het oorspronkelijke netwerk.

* Potentieel (prijzen): Initialiseer een potentiële functie `pi(v)` voor elk knooppunt `v` in `V`. Een gemeenschappelijk uitgangspunt is `pi(v) =0` voor alle `v`. De mogelijkheden zijn cruciaal voor het omgaan met negatieve kostencycli.

3. Algoritmestappen:

De kern van het Successive Shortest Path-algoritme is een iteratief proces:

A. Vind een bron en een wastafel: Selecteer een bronknooppunt `s` (waarbij `b(s)> 0`) en een sinkknooppunt `t` (waarbij `b(t) <0`) in het netwerk. Als dergelijke knooppunten niet bestaan, is het algoritme voltooid.

B. Kortste padberekening: Vind het kortste pad `P` van `s` naar `t` in het *restnetwerk* `G_f` met behulp van de *gereduceerde kosten*. De lagere kosten voor een boog `(u, v)` worden gedefinieerd als:

```

kosten_gereduceerd(u, v) =kosten(u, v) + pi(u) - pi(v)

```

* Het doel van het gebruik van lagere kosten is het elimineren van negatieve kostencycli. Als de potentiëlen `pi` zo worden gekozen dat `cost_reduced(u, v)>=0` voor alle bogen, dan kan het algoritme van Dijkstra worden gebruikt om het kortste pad te vinden.

* Als er na het toepassen van de mogelijkheden negatieve kosten blijven bestaan, kan het Bellman-Ford-algoritme worden gebruikt (maar dit is over het algemeen langzamer).

C. Vergroot de stroom: Laat `delta` het minimum zijn van:

* `b(s)` (het resterende aanbod bij bron `s`)

* `-b(t)` (de resterende vraag bij sink `t`)

* De minimale restcapaciteit langs het kortste pad `P`:`min{c_f(u, v) | (u, v) in P}`

Update de stroom langs het pad `P` met `delta`:

* Voor elke boog `(u, v)` in `P`:

* `f(u, v) =f(u, v) + delta`

* Update restcapaciteit:`c_f(u, v) =c(u, v) - f(u, v)`

* Als `(u, v)` bestaat in het oorspronkelijke netwerk, update dan de omgekeerde rand in het resterende netwerk:maak de rand `(v, u)` in `G_f` als deze niet bestaat met `c_f(v, u) =f(u, v)`.

D. Vraag en aanbod bijwerken:

* `b(s) =b(s) - delta`

* `b(t) =b(t) + delta`

e. Updatemogelijkheden (Bellman-Ford-variant): Dit is een *cruciale* stap om niet-negatieve lagere kosten te behouden en correct gedrag te garanderen. Nadat u de stroom heeft vergroot, moet u de potentiëlen bijwerken. Een gebruikelijke aanpak (vaak gebruikt in combinatie met Dijkstra na een eerste Bellman-Ford) is een Bellman-Ford-variant. Dit kan worden gedaan met behulp van de kortste padafstanden van de vorige iteratie, maar dan toegepast op alle hoekpunten. De sleutel is om ervoor te zorgen dat eventuele negatieve kostencycli die door de stroomvergroting worden geïntroduceerd, worden afgehandeld.

* Optie 1:volledige Bellman-Ford (minder efficiënt): Voer Bellman-Ford opnieuw uit vanaf een willekeurig knooppunt `r` naar alle andere knooppunten in `G_f` met gebruikmaking van de lagere kosten. Laat `d(v)` de kortste afstand zijn van `r` tot `v`. Werk de potentiëlen bij:`pi(v) =pi(v) - d(v)`. Dit garandeert `cost_reduced(u, v)>=0` voor alle bogen na de update, maar is relatief langzaam.

* Optie 2:Johnson's algoritme (efficiënt): Voer Bellman-Ford één keer uit om de initiële potentiëlen te berekenen. Gebruik vervolgens het algoritme van Dijkstra met behulp van de verlaagde kosten. Bereken na elke vergroting de potentiëlen opnieuw met behulp van het resultaat van Dijkstra.

F. Herhaal: Ga terug naar stap (a) en herhaal het proces totdat aan alle benodigdheden en eisen is voldaan (`b(v) =0` voor alle knooppunten `v`).

4. Beëindiging:

Het algoritme eindigt wanneer aan alle benodigdheden en eisen is voldaan. De resulterende stroom `f(u, v)` voor alle bogen `(u, v)` in het oorspronkelijke netwerk vertegenwoordigt de minimale kostenstroom.

Belangrijke gegevensstructuren:

* Aangrenzende lijst/matrix: Om het netwerk `G` en het restnetwerk `G_f` weer te geven. Aangrenzende lijsten zijn doorgaans efficiënter voor schaarse grafieken.

* Stroommatrix: Om de huidige stroom `f(u, v)` op elke boog op te slaan.

* Capaciteitsmatrix: Om de oorspronkelijke capaciteiten `c(u, v)` van elke boog op te slaan.

* Residuele capaciteitsmatrix: Om de restcapaciteiten `c_f(u, v)` in het restnetwerk op te slaan.

* Potentiële matrix: Om de potentiëlen `pi(v)` voor elk knooppunt op te slaan.

* Prioriteitswachtrij (hoop): Gebruikt in het algoritme van Dijkstra voor efficiënte berekening van de kortste pad.

Codeoverwegingen (voorbeeld van Python - vereenvoudigd):

```python

import heapq

def successive_shortest_path(grafiek, capaciteit, kosten, aanbod):

"""

Implementeert het opeenvolgende kortste pad-algoritme.

Argumenten:

grafiek:een woordenboek dat de grafiek weergeeft als een aangrenzende lijst.

Sleutels zijn knooppunten, waarden zijn lijsten van aangrenzende knooppunten.

capaciteit:een woordenboek dat de capaciteit van elke rand (u, v) weergeeft.

kosten:een woordenboek dat de kosten van elke rand (u, v) weergeeft.

aanbod:Een woordenboek dat het aanbod/de vraag van elk knooppunt weergeeft.

Positieve waarden zijn aanbod, negatieve waarden zijn vraag.

Retouren:

Een woordenboek dat de stroom op elke rand weergeeft, of Geen als er geen haalbare oplossing is.

"""

flow ={} # Initialiseer de flow naar nul

voor u in grafiek:

voor v in grafiek[u]:

stroom[(u, v)] =0

potentieel ={knooppunt:0 voor knooppunt in grafiek} # Initialiseer potentiëlen

terwijl waar:

bronnen =[knooppunt voor knooppunt in aanbod als aanbod[knooppunt]> 0]

sinks =[knooppunt voor knooppunt in aanbod als aanbod[knooppunt] <0]

zo niet bronnen of niet zinkt:

break # Alle vraag/aanbod tevreden

bron =bronnen[0]

zinken =zinken[0]

# Kortste pad via Dijkstra met lagere kosten

dist, prev =dijkstra(grafiek, capaciteit, kosten, potentieel, bron, put, stroom)

if dist[sink] ==float('inf'):# Geen pad gevonden, onhaalbaar

return Geen # Of behandel deze zaak anders

# Verbeter de stroom

delta =min(aanbod[bron], -aanbod[afvoer])

curr =zinken

while curr !=bron:

vorige_node =vorige[curr]

delta =min(delta, capaciteit[(vorige_knooppunt, huidige)] - stroom[(vorige_knooppunt, huidige)])

curr =vorig_knooppunt

curr =zinken

while curr !=bron:

vorige_node =vorige[curr]

flow[(vorige_node, curr)] +=delta

if (curr, prev_node) in capaciteit:

flow[(curr, prev_node)] -=delta # Achterwaartse stroom

anders:

flow[(curr, prev_node)] =-delta # Initialiseer indien nodig.

curr =vorig_knooppunt

aanbod[bron] -=delta

aanbod[sink] +=delta

# Update potentiëlen met behulp van de afstanden van Dijkstra

voor knooppunt in grafiek:

potentieel[knooppunt] +=dist[knooppunt]

retourstroom

def dijkstra(grafiek, capaciteit, kosten, potentieel, bron, put, stroom):

"""

Dijkstra's algoritme met lagere kosten.

"""

dist ={knooppunt:float('inf') voor knooppunt in grafiek}

prev ={knooppunt:Geen voor knooppunt in grafiek}

dist[bron] =0

pq =[(0, bron)] # Prioriteitswachtrij (afstand, knooppunt)

terwijl pq:

d, u =heapq.heappop(pq)

if d> dist[u]:# Luie verwijdering

doorgaan

voor v in grafiek[u]:

# Houd alleen rekening met randen met een restcapaciteit> 0

als capaciteit[(u, v)] - stroom[(u, v)]> 0:

gereduceerde_kosten =kosten[(u, v)] + potentieel[u] - potentieel[v]

als dist[v]> dist[u] + gereduceerde_kosten:

dist[v] =dist[u] + verlaagde_kosten

vorige[v] =u

heapq.heappush(pq, (dist[v], v))

retour afst, vorige

Voorbeeldgebruik:

grafiek ={

's':['a', 'b'],

'a':['b', 't'],

'b':['t'],

'T':[]

}

capaciteit ={

('s', 'een'):10,

('s', 'b'):5,

('a', 'b'):4,

('een', 't'):8,

('b', 't'):12

}

kosten ={

('s', 'een'):2,

('s', 'b'):4,

('a', 'b'):1,

('a', 't'):7,

('b', 't'):5

}

aanbod ={

's':15,

'een':0,

'b':0,

't':-15

}

flow =successive_shortest_path(grafiek, capaciteit, kosten, aanbod)

als stroom:

print("Stroomtoewijzing:", flow)

# Bereken de totale kosten

totale_kosten =som(stroom[(u, v)] * kosten[(u, v)] voor (u, v) in stroom)

print("Totale kosten:", total_cost)

anders:

print("Geen haalbare oplossing gevonden.")

```

Belangrijke overwegingen:

* Negatieve kostencycli: Het SSP-algoritme is ontworpen om met negatieve kostencycli om te gaan. De potentiële functie `pi(v)` is hiervoor cruciaal. Als u de potentiëlen niet correct bijwerkt, convergeert het algoritme mogelijk niet of levert het een onjuiste oplossing op.

* Dijkstra's versus Bellman-Ford:

*Als je *altijd* niet-negatieve lagere kosten handhaaft, is het algoritme van Dijkstra veel sneller in het vinden van de kortste paden. Dit is het ideale scenario en wordt meestal bereikt met de juiste potentiële updates.

* Als u niet-negatieve lagere kosten niet kunt garanderen, *moet* u Bellman-Ford gebruiken, wat langzamer is (O(V * E) tijdcomplexiteit). Het wordt vaak alleen gebruikt voor de initiële potentiaalberekening.

* Residueel netwerk: Het correct onderhouden van het restnetwerk is essentieel. Vergeet niet om achterranden te creëren wanneer de stroom langs een boog wordt geduwd.

* Computationele complexiteit: De complexiteit van het SSP-algoritme hangt af van het gebruikte kortste pad-algoritme en het aantal iteraties. In het ergste geval kan het pseudo-polynoom zijn als de capaciteiten groot zijn.

* Alternatieve algoritmen: Voor grootschalige problemen met minimale kostenstromen zijn andere algoritmen, zoals het Network Simplex-algoritme, vaak efficiënter.

Samenvattend is het Successive Shortest Path-algoritme een krachtige en conceptueel duidelijke methode voor het oplossen van problemen met minimale kostenstromen. Het begrijpen van de rollen van het restnetwerk, de lagere kosten en de potentiële functie is de sleutel tot een correcte implementatie ervan. Kies het juiste kortste pad-algoritme (Dijkstra of Bellman-Ford) op basis van de vraag of u niet-negatieve lagere kosten kunt garanderen. Vergeet niet om de updates in vraag en aanbod af te handelen en ook de potentiëlen correct bij te werken.