algorithm
Bellman-Ford algoritme

Opmerkingen

Algoritme met één bron, kortste pad (gegeven dat er een negatieve cyclus in een grafiek is)

Voordat u dit voorbeeld leest, moet u een kort idee hebben van edge-relaxatie. Je kunt het hier leren

Bellman-Ford Algorithm berekent de kortste paden van een hoekpunt van een enkele bron naar alle andere hoekpunten in een gewogen digraph. Hoewel het langzamer is dan het algoritme van Dijkstra , werkt het in de gevallen waarin het gewicht van de rand negatief is en vindt het ook een negatieve gewichtscyclus in de grafiek. Het probleem met het algoritme van Dijkstra is dat als er een negatieve cyclus is, je de cyclus steeds opnieuw doorloopt en de afstand tussen twee hoekpunten blijft verkleinen.

Het idee van dit algoritme is om alle randen van deze grafiek één voor één in een willekeurige volgorde te doorlopen. Het kan elke willekeurige volgorde zijn. Maar u moet ervoor zorgen dat als uv (waarbij u en v twee hoekpunten in een grafiek zijn) een van uw orders is, er een rand moet zijn van u naar v . Gewoonlijk wordt het rechtstreeks uit de volgorde van de ingevoerde gegevens gehaald. Nogmaals, elke willekeurige volgorde zal werken.

Na het selecteren van de volgorde zullen we de randen ontspannen volgens de ontspanningsformule. Voor een gegeven rand uv gaande van u naar v het ontspannen formule:

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

Dat wil zeggen, als de afstand van bron tot een hoekpunt u + het gewicht van de rand uv kleiner is dan de afstand van bron tot een ander hoekpunt v , werken we de afstand van bron tot v bij . We moeten de randen op de meeste (V-1) tijden ontspannen waarbij V het aantal randen in de grafiek is. Waarom (V-1) vraag je? We zullen het in een ander voorbeeld uitleggen. We gaan ook het ouderpunt van elk hoekpunt bijhouden, dat is wanneer we een voorsprong ontspannen, zullen we instellen:

parent[v] = u

Het betekent dat we een ander korter pad hebben gevonden om v via u te bereiken. Dit hebben we later nodig om het kortste pad van de bron naar het bestemde hoekpunt af te drukken.

Laten we een voorbeeld bekijken. We hebben een grafiek:

We hebben 1 geselecteerd als de bron vertex. We willen het kortste pad van de bron naar alle andere hoekpunten ontdekken.

Eerst is d [1] = 0 omdat het de bron is. En rust is oneindig , omdat we hun afstand nog niet kennen.

We zullen de randen in deze volgorde ontspannen:

+--------+--------+--------+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

U kunt elke gewenste volgorde aannemen. Als we de randen eenmaal ontspannen , wat krijgen we dan? We krijgen de afstand van de bron tot alle andere hoekpunten van het pad dat maximaal 1 rand gebruikt. Laten we nu de randen ontspannen en de waarden van d [] bijwerken. We krijgen:

1. d [4] + kosten [4] [5] = oneindig + 7 = oneindig . We kunnen deze niet bijwerken.
2. d [2] + kosten [3] [4] = oneindig . We kunnen deze niet bijwerken.
3. d [1] + kosten [1] [2] = 0 + 2 = 2 < d [2] . Dus d [2] = 2 . Ook ouder [2] = 1 .
4. d [1] + kosten [1] [4] = 4 . Dus d [4] = 4 < d [4] . ouder [4] = 1 .
5. d [4] + kosten [4] [6] = 9 . d [6] = 9 < d [6] . ouder [6] = 4 .
6. d [2] + kosten [2] [2] = oneindig . We kunnen deze niet bijwerken.

We konden sommige hoekpunten niet bijwerken, omdat de voorwaarde d[u] + cost[u][v] < d[v] niet overeenkwam. Zoals we eerder hebben gezegd, hebben we de paden van bron naar andere knooppunten gevonden met maximaal 1 rand.

Onze tweede iteratie geeft ons het pad met behulp van 2 knooppunten. We krijgen:

1. d [4] + kosten [4] [5] = 12 < d [5] . d [5] = 12 . ouder [5] = 4 .
2. d [3] + kosten [3] [4] = 1 < d [4] . d [4] = 1 . ouder [4] = 3 .
3. d [3] blijft ongewijzigd.
4. d [4] blijft ongewijzigd.
5. d [4] + kosten [4] [6] = 6 < d [6] . d [6] = 6 . ouder [6] = 4 .
6. d [3] blijft ongewijzigd.

Onze grafiek ziet eruit als:

Onze 3e iteratie zal alleen hoekpunt 5 bijwerken, waarbij d [5] 8 zal zijn. Onze grafiek ziet eruit als:

Hierna hebben we, ongeacht het aantal iteraties dat we doen, dezelfde afstanden. We houden dus een vlag die controleert of er een update plaatsvindt of niet. Als dit niet het geval is, breken we gewoon de lus. Onze pseudo-code zal zijn:

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

Om de negatieve cyclus bij te houden, kunnen we onze code wijzigen met behulp van de hier beschreven procedure. Onze ingevulde pseudo-code zal zijn:

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return d

Afdrukken pad:

Om het kortste pad naar een hoekpunt af te drukken, gaan we terug naar het bovenliggende element totdat we NULL vinden en vervolgens de hoekpunten afdrukken. De pseudo-code zal zijn:

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

complexiteit:

Omdat we de randen maximaal (V-1) keer moeten ontspannen, zal de tijdcomplexiteit van dit algoritme gelijk zijn aan O (V * E), waarbij E het aantal randen aangeeft, als we adjacency list om de grafiek weer te geven. Als echter adjacency matrix wordt gebruikt om de grafiek weer te geven, is de tijdcomplexiteit O (V ^ 3) . Reden is dat we alle randen in de O (E) -tijd kunnen doorlopen wanneer de adjacency list wordt gebruikt, maar het duurt O (V ^ 2) wanneer de adjacency matrix wordt gebruikt.

Waarom moeten we bij de meeste (V-1) tijden alle randen ontspannen

Om dit voorbeeld te begrijpen, wordt het aanbevolen om een kort idee te hebben van het Bellman-Ford algoritme voor het kortste pad met één bron, dat hier te vinden is

In het Bellman-Ford-algoritme moeten we alle randen van de grafiek ontspannen om het kortste pad te vinden. Dit proces wordt maximaal (V-1) keer herhaald, waarbij V het aantal hoekpunten in de grafiek is.

Het aantal iteraties dat nodig is om het kortste pad van bron naar alle andere hoekpunten te vinden, hangt af van de volgorde die we selecteren om de randen te ontspannen .

Laten we een voorbeeld bekijken:

Hier, de bron vertex is 1. We zullen het vinden van de kortste afstand tussen de bron en alle andere hoekpunten. We kunnen duidelijk zien dat, om vertex 4 te bereiken, in het ergste geval (V-1) randen nodig zijn. Nu, afhankelijk van de volgorde waarin de randen worden ontdekt, kan het (V-1) keer duren om hoekpunt 4 te ontdekken. Heb je het niet gekregen? Laten we het Bellman-Ford-algoritme gebruiken om hier het kortste pad te vinden:

We gaan deze volgorde gebruiken:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

Voor onze eerste iteratie:

1. d [3] + kosten [3] [4] = oneindig . Het zal niets veranderen.
2. d [2] + kosten [2] [3] = oneindig . Het zal niets veranderen.
3. d [1] + kosten [1] [2] = 2 < d [2] . d [2] = 2 . ouder [2] = 1 .

We kunnen zien dat ons ontspanningsproces alleen d [2] heeft veranderd . Onze grafiek ziet eruit als:

Tweede iteratie:

1. d [3] + kosten [3] [4] = oneindig . Het zal niets veranderen.
2. d [2] + kosten [2] [3] = 5 < d [3] . d [3] = 5 . ouder [3] = 2.
3. Het zal niet worden gewijzigd.

Deze keer veranderde het relaxatieproces d [3] . Onze grafiek ziet eruit als:

Derde iteratie:

1. d [3] + kosten [3] [4] = 7 < d [4] . d [4] = 7 . ouder [4] = 3 .
2. Het zal niet worden gewijzigd.
3. Het zal niet worden gewijzigd.

Onze derde iteratie heeft uiteindelijk de kortste weg naar 4 van 1 gevonden . Onze grafiek ziet eruit als:

Er waren dus 3 iteraties nodig om de kortste weg te vinden. Na deze, ongeacht hoe vaak we de randen ontspannen , blijven de waarden in d [] hetzelfde. Als we nu een andere reeks overwegen:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

We zouden krijgen:

1. d [1] + kosten [1] [2] = 2 < d [2] . d [2] = 2 .
2. d [2] + kosten [2] [3] = 5 < d [3] . d [3] = 5 .
3. d [3] + kosten [3] [4] = 7 < d [4] . d [4] = 5 .

Onze allereerste iteratie heeft het kortste pad gevonden van bron naar alle andere knooppunten. Een andere reeks 1-> 2 , 3-> 4 , 2-> 3 is mogelijk, wat ons de kortste weg geeft na 2 iteraties. We kunnen tot de beslissing komen dat, ongeacht hoe we de volgorde regelen, er niet meer dan 3 iteraties nodig zijn om in dit voorbeeld de kortste weg van de bron te vinden.

We kunnen concluderen dat, in het beste geval, 1 iteratie nodig is om het kortste pad van de bron te vinden . In het ergste geval zijn iteraties nodig (V-1) , daarom herhalen we het ontspanningsproces (V-1) keer.

Negatieve cyclus in een grafiek detecteren

Om dit voorbeeld te begrijpen, wordt het aanbevolen om een kort idee te hebben van het Bellman-Ford-algoritme dat u hier kunt vinden

Met behulp van het Bellman-Ford-algoritme kunnen we detecteren of er een negatieve cyclus in onze grafiek is. We weten dat we, om het kortste pad te vinden, alle randen van de grafiek (V-1) keer moeten ontspannen , waarbij V het aantal hoekpunten in een grafiek is. We hebben al gezien dat we in dit voorbeeld na (V-1) iteraties d [] niet kunnen bijwerken, ongeacht het aantal iteraties dat we doen. Of kunnen we?

Als er een negatieve cyclus in een grafiek is, zelfs na (V-1) iteraties, kunnen we d [] bijwerken. Dit gebeurt omdat voor elke iteratie het doorlopen van de negatieve cyclus altijd de kosten van het kortste pad verlaagt. Daarom beperkt het Bellman-Ford-algoritme het aantal iteraties tot (V-1) . Als we hier het algoritme van Dijkstra gebruiken, zitten we vast in een eindeloze lus. Laten we ons echter concentreren op het vinden van een negatieve cyclus.

Laten we aannemen dat we een grafiek hebben:

Laten we hoekpunt 1 als bron kiezen . Nadat we Bellman-Ford's algoritme voor de kortste weg met één bron op de grafiek hebben toegepast, zullen we de afstanden van de bron tot alle andere hoekpunten ontdekken.

Zo ziet de grafiek eruit na (V-1) = 3 iteraties. Het zou het resultaat moeten zijn, want er zijn 4 randen, we hebben maximaal 3 iteraties nodig om de kortste weg te vinden. Dus dit is het antwoord, of er is een negatieve gewichtscyclus in de grafiek. Om te vinden dat we na (V-1) iteraties nog een laatste iteratie uitvoeren en als de afstand blijft afnemen, betekent dit dat er zeker een negatieve gewichtscyclus in de grafiek is.

Voor dit voorbeeld: als we 2-3 aanvinken, geeft d [2] + kosten [2] [3] ons 1 die kleiner is dan d [3] . We kunnen dus concluderen dat er een negatieve cyclus in onze grafiek zit.

Dus hoe komen we de negatieve cyclus te weten? We hebben een kleine wijziging aangebracht aan de Bellman-Ford-procedure:

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

Dit is hoe we erachter komen of er een negatieve cyclus in een grafiek is. We kunnen ook Bellman-Ford algoritme aanpassen om negatieve cycli bij te houden.