algorithm
Bellman – Ford algoritm

Anmärkningar

Algoritm med kortaste sökvägen med en källa (med tanke på att det finns en negativ cykel i en graf)

Innan du läser detta exempel krävs det en kort uppfattning om kantavslappning. Du kan lära dig det här

Bellman-Ford Algoritm beräknar de kortaste vägarna från en enda källvinkel till alla andra vertikaler i en vägd digraf. Trots att den är långsammare än Dijkstra's algoritm , fungerar den i de fall då vikten på kanten är negativ och den hittar också negativ viktcykel i diagrammet. Problemet med Dijkstra's algoritm är, om det finns en negativ cykel, fortsätter du igenom cykeln om och om igen och fortsätter att minska avståndet mellan två hörn.

Tanken med denna algoritm är att gå igenom alla kanter på denna graf en och en i en slumpmässig ordning. Det kan vara vilken slumpmässig ordning som helst. Men du måste se till att om uv (där u och v är två vertikaler i en graf) är en av dina beställningar, måste det finnas en kant från u till v . Vanligtvis tas det direkt från den angivna inmatningen. Återigen kommer alla slumpmässiga ordningar att fungera.

Efter att vi har valt ordern kommer vi att slappna av kanterna enligt avslappningsformeln. För en given kant uv som går från u till v är relaxationsformeln:

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

Det vill säga, om avståndet från källa till något toppunkt u + vikten på kanten uv är mindre än avståndet från källa till ett annat toppunkt v , uppdaterar vi avståndet från källa till v . Vi måste slappna av kanterna på det mesta (V-1) gånger där V är antalet kanter i diagrammet. Varför (V-1) frågar du? Vi förklarar det i ett annat exempel. Vi kommer också att hålla reda på moderkoden för alla toppningar, det vill säga när vi slappnar av en kant, kommer vi att sätta:

parent[v] = u

Det betyder att vi har hittat en annan kortare väg att nå v via u . Vi kommer att behöva detta senare för att skriva ut den kortaste vägen från källa till det avsedda toppunktet.

Låt oss titta på ett exempel. Vi har en graf:

Vi har valt 1 som källkoder . Vi vill ta reda på den kortaste vägen från källan till alla andra vertikaler.

Först, d [1] = 0 eftersom det är källan. Och vila är oändlighet , för vi vet inte deras avstånd än.

Vi kommer att slappna av kanterna i denna sekvens:

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

Du kan ta vilken sekvens du vill ha. Om vi slappnar av kanterna en gång, vad får vi då? Vi får avståndet från källan till alla andra vertikaler på banan som använder högst 1 kant. Låt oss nu slappna av kanterna och uppdatera värdena på d [] . Vi får:

1. d [4] + kostnad [4] [5] = oändlighet + 7 = oändlighet . Vi kan inte uppdatera den här.
2. d [2] + kostnad [3] [4] = oändlighet . Vi kan inte uppdatera den här.
3. d [1] + kostnad [1] [2] = 0 + 2 = 2 < d [2] . Så d [2] = 2 . Även förälder [2] = 1 .
4. d [1] + kostnad [1] [4] = 4 . Så d [4] = 4 < d [4] . förälder [4] = 1 .
5. d [4] + kostnad [4] [6] = 9 . d [6] = 9 < d [6] . förälder [6] = 4 .
6. d [2] + kostnad [2] [2] = oändlighet . Vi kan inte uppdatera den här.

Vi kunde inte uppdatera vissa topppunkter, eftersom villkoret d[u] + cost[u][v] < d[v] inte matchade. Som vi har sagt tidigare hittade vi banorna från källa till andra noder med max 1 kant.

Vår andra iteration kommer att ge oss sökvägen med två noder. Vi får:

1. d [4] + kostnad [4] [5] = 12 < d [5] . d [5] = 12 . förälder [5] = 4 .
2. d [3] + kostnad [3] [4] = 1 < d [4] . d [4] = 1 . förälder [4] = 3 .
3. d [3] förblir oförändrad.
4. d [4] förblir oförändrad.
5. d [4] + kostnad [4] [6] = 6 < d [6] . d [6] = 6 . förälder [6] = 4 .
6. d [3] förblir oförändrad.

Vår graf ser ut som:

Vår tredje iteration uppdaterar endast topp 5 , där d [5] är 8 . Vår graf ser ut som:

Efter detta oavsett hur många iterationer vi gör, har vi samma avstånd. Så vi kommer att hålla en flagga som kontrollerar om någon uppdatering äger rum eller inte. Om det inte gör det kommer vi helt enkelt att bryta slingan. Vår pseudokod kommer att vara:

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

För att hålla reda på negativ cykel kan vi ändra vår kod med hjälp av proceduren som beskrivs här . Vår ifyllda pseudokod kommer att vara:

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

Utskriftsväg:

För att skriva ut den kortaste sökvägen till ett toppunkt, återgår vi till dess överordnade tills vi hittar NULL och skriver sedan ut topparna. Pseudokoden kommer att vara:

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

Komplexitet:

Eftersom vi måste slappna av kanterna maximalt (V-1) gånger kommer tidskomplexiteten för denna algoritm att vara lika med O (V * E) där E anger antalet kanter, om vi använder adjacency list att representera grafen. Om adjacency matrix används för att representera diagrammet är emellertid tidskomplexiteten O (V ^ 3) . Anledningen är att vi kan iterera igenom alla kanter i O (E) adjacency list när adjacency list används, men det tar O (V ^ 2) tid när adjacency matrix används.

Varför måste vi koppla av alla kanter på de flesta (V-1) gånger

För att förstå detta exempel rekommenderas det att ha en kort idé om Bellman-Ford kortaste sökvägsalgoritm som kan hittas här

I Bellman-Ford algoritm, för att ta reda på den kortaste vägen, måste vi koppla av alla kanter på grafen. Denna process upprepas högst (V-1) gånger, där V är antalet vertikaler i diagrammet.

Antalet iterationer som behövs för att ta reda på den kortaste vägen från källa till alla andra toppar beror på ordningen som vi väljer för att koppla av kanterna.

Låt oss ta en titt på ett exempel:

Här är källkoden 1. Vi kommer att ta reda på det kortaste avståndet mellan källan och alla andra vertikaler. Vi kan tydligt se att för att nå topp 4 , i värsta fall, kommer det att ta (V-1) kanter. Beroende på i vilken ordning kanterna upptäcks kan det ta (V-1) gånger att upptäcka toppunkt 4 . Fick du det inte? Låt oss använda Bellman-Ford-algoritmen för att ta reda på den kortaste vägen här:

Vi kommer att använda denna sekvens:

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

För vår första iteration:

1. d [3] + kostnad [3] [4] = oändlighet . Det kommer inte att ändra någonting.
2. d [2] + kostnad [2] [3] = oändlighet . Det kommer inte att ändra någonting.
3. d [1] + kostnad [1] [2] = 2 < d [2] . d [2] = 2 . förälder [2] = 1 .

Vi kan se att vår avkopplingsprocess bara förändrats d [2] . Vår graf ser ut som:

Andra iterationen:

1. d [3] + kostnad [3] [4] = oändlighet . Det kommer inte att ändra någonting.
2. d [2] + kostnad [2] [3] = 5 < d [3] . d [3] = 5 . förälder [3] = 2.
3. Det kommer inte att ändras.

Denna gång förändrade avkopplingsprocessen d [3] . Vår graf ser ut som:

Tredje iteration:

1. d [3] + kostnad [3] [4] = 7 < d [4] . d [4] = 7 . förälder [4] = 3 .
2. Det kommer inte att ändras.
3. Det kommer inte att ändras.

Vår tredje iteration hittade äntligen den kortaste vägen till 4 från 1 . Vår graf ser ut som:

Så tog det 3 iterationer att ta reda på den kortaste vägen. Efter detta, oavsett hur många gånger vi slappnar av kanterna, kommer värdena i d [] att förbli desamma. Om vi nu övervägde en annan sekvens:

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

Vi skulle få:

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

Vår allra första iteration har hittat den kortaste vägen från källa till alla andra noder. En annan sekvens 1-> 2 , 3-> 4 , 2-> 3 är möjlig, vilket kommer att ge oss den kortaste vägen efter 2 iterationer. Vi kan komma till beslutet att oavsett hur vi arrangerar sekvensen, kommer det inte ta mer än 3 iterationer att ta reda på kortaste vägen från källan i det här exemplet.

Vi kan konstatera att, för bästa fall kommer det att ta en iteration att ta reda på den kortaste vägen från källan. I värsta fall kommer det att ta (V-1) iterationer, varför vi upprepar processen för avkoppling (V-1) gånger.

Upptäcka negativ cykel i en graf

För att förstå detta exempel rekommenderas det att ha en kort uppfattning om Bellman-Ford algoritm som du hittar här

Med hjälp av Bellman-Ford-algoritmen kan vi upptäcka om det finns en negativ cykel i vår graf. Vi vet att för att ta reda på den kortaste vägen måste vi koppla av alla kanter på grafen (V-1) gånger, där V är antalet vertikaler i en graf. Vi har redan sett att vi i det här exemplet efter (V-1) iterationer inte kan uppdatera d [] , oavsett hur många iterationer vi gör. Eller kan vi?

Om det finns en negativ cykel i en graf, även efter (V-1) iterationer, kan vi uppdatera d [] . Detta händer eftersom genomgående genom den negativa cykeln för varje iteration alltid minskar kostnaden för den kortaste vägen. Det är därför Bellman-Ford-algoritmen begränsar antalet iterationer till (V-1) . Om vi använde Dijkstra's algoritm här, skulle vi fastna i en oändlig slinga. Låt oss dock koncentrera oss på att hitta negativ cykel.

Låt oss anta att vi har en graf:

Låt oss välja topp 1 som källa . Efter att ha använt Bellman-Fords kortaste banalgoritm med en enda källa på diagrammet kommer vi att ta reda på avståndet från källan till alla andra vertikaler.

Så här ser grafen ut efter (V-1) = 3 iterationer. Det borde vara resultatet eftersom det finns fyra kanter, vi behöver högst 3 iterationer för att ta reda på den kortaste vägen. Så antingen är detta svaret, eller så finns det en negativ viktcykel i diagrammet. För att upptäcka att vi, efter (V-1) iterationer, gör en ytterligare sista iteration och om avståndet fortsätter att minska, betyder det att det definitivt finns en negativ viktcykel i diagrammet.

För detta exempel: om vi kontrollerar 2-3 , kommer d [2] + kostnad [2] [3] att ge oss 1 som är mindre än d [3] . Så vi kan dra slutsatsen att det finns en negativ cykel i vår graf.

Så hur tar vi reda på den negativa cykeln? Vi gör lite modifiering av Bellman-Ford-proceduren:

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"

Så här finner vi ut om det finns en negativ cykel i en graf. Vi kan också ändra Bellman-Ford-algoritmen för att hålla reda på negativa cykler.