algorithm
Algoritmo di Bellman-Ford

Osservazioni

Algoritmo del percorso più breve della singola sorgente (dato che c'è un ciclo negativo in un grafico)

Prima di leggere questo esempio, è necessario avere una breve idea sul rilassamento dei bordi. Puoi imparare da qui

L' algoritmo Bellman-Ford calcola i cammini più corti da un vertice a sorgente singola a tutti gli altri vertici in un digrafo ponderato. Anche se è più lento dell'algoritmo di Dijkstra , funziona nei casi in cui il peso del bordo è negativo e trova anche un ciclo di peso negativo nel grafico. Il problema con Algorithm di Dijkstra è, se c'è un ciclo negativo, si continua a passare attraverso il ciclo ancora e ancora e si continua a ridurre la distanza tra due vertici.

L'idea di questo algoritmo è di esaminare tutti i bordi di questo grafico uno per uno in un ordine casuale. Può essere qualsiasi ordine casuale. Ma devi assicurarti che se uv (dove tu v sono due vertici in un grafico) è uno dei tuoi ordini, allora ci deve essere un vantaggio da u a v . Di solito è preso direttamente dall'ordine dell'input dato. Di nuovo, qualsiasi ordine casuale funzionerà.

Dopo aver selezionato l'ordine, rilasseremo i bordi in base alla formula di rilassamento. Per un dato limite uv da u a v la formula di rilassamento è:

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

Cioè, se la distanza dalla sorgente a qualsiasi vertice u + il peso del bordo uv è inferiore alla distanza dalla sorgente a un altro vertice v , aggiorniamo la distanza dalla sorgente a v . Abbiamo bisogno di rilassare i bordi al massimo (V-1) volte in cui V è il numero di spigoli nel grafico. Perché (V-1) chiedi? Lo spiegheremo in un altro esempio. Inoltre stiamo andando a tenere traccia del vertice genitore di qualsiasi vertice, cioè quando rilassiamo un margine, imposteremo:

parent[v] = u

Significa che abbiamo trovato un altro percorso più breve per raggiungere v via u . Avremo bisogno di questo in seguito per stampare il percorso più breve dalla sorgente al vertice destinato.

Diamo un'occhiata a un esempio. Abbiamo un grafico:

Abbiamo selezionato 1 come vertice sorgente . Vogliamo scoprire il percorso più breve dalla sorgente a tutti gli altri vertici.

All'inizio, d [1] = 0 perché è la fonte. E il riposo è infinito , perché non conosciamo ancora la loro distanza.

Rilasceremo i bordi in questa sequenza:

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

Puoi prendere qualsiasi sequenza tu voglia. Se rilassiamo i bordi una volta, cosa otteniamo? Otteniamo la distanza dalla sorgente a tutti gli altri vertici del percorso che utilizza al massimo 1 bordo. Ora rilassiamo i bordi e aggiorniamo i valori di d [] . Noi abbiamo:

1. d [4] + costo [4] [5] = infinito + 7 = infinito . Non possiamo aggiornare questo.
2. d [2] + costo [3] [4] = infinito . Non possiamo aggiornare questo.
3. d [1] + costo [1] [2] = 0 + 2 = 2 < d [2] . Quindi d [2] = 2 . Anche genitore [2] = 1 .
4. d [1] + costo [1] [4] = 4 . Quindi d [4] = 4 < d [4] . genitore [4] = 1 .
5. d [4] + costo [4] [6] = 9 . d [6] = 9 < d [6] . genitore [6] = 4 .
6. d [2] + costo [2] [2] = infinito . Non possiamo aggiornare questo.

Non è stato possibile aggiornare alcuni vertici, perché la condizione d[u] + cost[u][v] < d[v] non corrisponde. Come abbiamo detto prima, abbiamo trovato i percorsi dalla sorgente ad altri nodi usando il massimo 1 spigolo.

La nostra seconda iterazione ci fornirà il percorso utilizzando 2 nodi. Noi abbiamo:

1. d [4] + costo [4] [5] = 12 < d [5] . d [5] = 12 . genitore [5] = 4 .
2. d [3] + costo [3] [4] = 1 < d [4] . d [4] = 1 . genitore [4] = 3 .
3. d [3] rimane invariato.
4. d [4] rimane invariato.
5. d [4] + costo [4] [6] = 6 < d [6] . d [6] = 6 . genitore [6] = 4 .
6. d [3] rimane invariato.

Il nostro grafico sarà simile a:

La nostra terza iterazione aggiornerà solo il vertice 5 , dove d [5] sarà 8 . Il nostro grafico sarà simile a:

Dopo questo, indipendentemente da quante iterazioni facciamo, avremo le stesse distanze. Quindi manterremo una bandiera che controlla se si verifica o meno un aggiornamento. In caso contrario, interromperemo semplicemente il ciclo. Il nostro pseudo-codice sarà:

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

Per tenere traccia del ciclo negativo, possiamo modificare il nostro codice utilizzando la procedura descritta qui . Il nostro pseudo-codice completato sarà:

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

Percorso di stampa:

Per stampare il percorso più breve verso un vertice, torneremo al suo genitore finché non troviamo NULL e quindi stampiamo i vertici. Lo pseudo-codice sarà:

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

Complessità:

Poiché abbiamo bisogno di rilassare i bordi al massimo (V-1) volte, la complessità temporale di questo algoritmo sarà uguale a O (V * E) dove E indica il numero di spigoli, se usiamo l' adjacency list per rappresentare il grafico. Tuttavia, se la adjacency matrix viene utilizzata per rappresentare il grafico, la complessità temporale sarà O (V ^ 3) . La ragione è che possiamo scorrere tutti i bordi nel tempo O (E) quando viene usata la adjacency list , ma ci vuole tempo O (V ^ 2) quando si usa la adjacency matrix .

Perché abbiamo bisogno di rilassare tutti i bordi al massimo (V-1) volte

Per comprendere questo esempio, si consiglia di avere una breve idea sull'algoritmo del percorso più breve della singola fonte Bellman-Ford che può essere trovato qui

Nell'algoritmo di Bellman-Ford, per scoprire il percorso più breve, abbiamo bisogno di rilassare tutti i bordi del grafico. Questo processo viene ripetuto al massimo (V-1) volte, dove V è il numero di vertici nel grafico.

Il numero di iterazioni necessarie per trovare il percorso più breve dalla sorgente a tutti gli altri vertici dipende dall'ordine che selezioniamo per rilassare i bordi.

Diamo un'occhiata a un esempio:

Qui, il vertice sorgente è 1. Scopriremo la distanza più breve tra la sorgente e tutti gli altri vertici. Possiamo chiaramente vedere che, per raggiungere il vertice 4 , nel caso peggiore, ci vorranno i bordi (V-1) . Ora, a seconda dell'ordine in cui vengono scoperti i bordi, potrebbe essere necessario (V-1) volte per scoprire il vertice 4 . Non l'hai capito? Usiamo l'algoritmo di Bellman-Ford per scoprire il percorso più breve qui:

Useremo questa sequenza:

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

Per la nostra prima iterazione:

1. d [3] + costo [3] [4] = infinito . Non cambierà nulla.
2. d [2] + costo [2] [3] = infinito . Non cambierà nulla.
3. d [1] + costo [1] [2] = 2 < d [2] . d [2] = 2 . genitore [2] = 1 .

Possiamo vedere che il nostro processo di rilassamento è cambiato solo d [2] . Il nostro grafico sarà simile a:

Seconda iterazione:

1. d [3] + costo [3] [4] = infinito . Non cambierà nulla.
2. d [2] + costo [2] [3] = 5 < d [3] . d [3] = 5 . genitore [3] = 2.
3. Non sarà cambiato.

Questa volta il processo di rilassamento è cambiato d [3] . Il nostro grafico sarà simile a:

Terza iterazione:

1. d [3] + costo [3] [4] = 7 < d [4] . d [4] = 7 . genitore [4] = 3 .
2. Non sarà cambiato.
3. Non sarà cambiato.

La nostra terza iterazione finalmente ha scoperto il percorso più breve per 4 da 1 . Il nostro grafico sarà simile a:

Quindi, ci sono volute 3 iterazioni per scoprire il percorso più breve. Dopo questo, non importa quante volte rilassiamo i bordi, i valori in d [] rimarranno gli stessi. Ora, se considerassimo un'altra sequenza:

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

Otterremo:

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

La nostra prima iterazione ha trovato il percorso più breve dalla sorgente a tutti gli altri nodi. Un'altra sequenza 1-> 2 , 3-> 4 , 2-> 3 è possibile, che ci darà il percorso più breve dopo 2 iterazioni. Possiamo prendere la decisione che, indipendentemente da come organizziamo la sequenza, non ci vorranno più di 3 iterazioni per scoprire il percorso più breve dalla fonte in questo esempio.

Possiamo concludere che, per il caso migliore, occorrerà 1 iterazione per trovare il percorso più breve dalla fonte . Nel peggiore dei casi, ci vorranno iterazioni (V-1) , motivo per cui ripetiamo il processo di rilassamento (V-1) volte.

Rilevamento del ciclo negativo in un grafico

Per comprendere questo esempio, si consiglia di avere una breve idea dell'algoritmo di Bellman-Ford che può essere trovato qui

Utilizzando l'algoritmo di Bellman-Ford, possiamo rilevare se c'è un ciclo negativo nel nostro grafico. Sappiamo che, per scoprire il percorso più breve, abbiamo bisogno di rilassare tutti i bordi del grafico (V-1) volte, dove V è il numero di vertici in un grafico. Abbiamo già visto che in questo esempio , dopo le iterazioni (V-1) , non possiamo aggiornare d [] , non importa quante iterazioni facciamo. O possiamo?

Se c'è un ciclo negativo in un grafico, anche dopo iterazioni (V-1) , possiamo aggiornare d [] . Questo accade perché per ogni iterazione, attraversando il ciclo negativo diminuisce sempre il costo del percorso più breve. Ecco perché l'algoritmo di Bellman-Ford limita il numero di iterazioni a (V-1) . Se usassimo l'algoritmo di Dijkstra qui, saremmo bloccati in un ciclo infinito. Tuttavia, concentriamoci sulla ricerca del ciclo negativo.

Supponiamo di avere un grafico:

Prendiamo il vertice 1 come fonte . Dopo aver applicato l'algoritmo del percorso più breve della sorgente singola di Bellman-Ford al grafico, scopriremo le distanze dalla sorgente a tutti gli altri vertici.

Ecco come appare il grafico dopo (V-1) = 3 iterazioni. Dovrebbe essere il risultato dato che ci sono 4 spigoli, abbiamo bisogno al massimo di 3 iterazioni per scoprire il percorso più breve. Quindi, o questa è la risposta, o c'è un ciclo di peso negativo nel grafico. Per trovarlo, dopo le iterazioni (V-1) , facciamo un'ultima iterazione finale e se la distanza continua a diminuire, significa che c'è sicuramente un ciclo di peso negativo nel grafico.

Per questo esempio: se controlliamo 2-3 , d [2] + costo [2] [3] ci darà 1 che è minore di d [3] . Quindi possiamo concludere che c'è un ciclo negativo nel nostro grafico.

Quindi, come possiamo scoprire il ciclo negativo? Facciamo un po 'di modifica alla procedura di Bellman-Ford:

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"

Questo è il modo in cui scopriamo se c'è un ciclo negativo in un grafico. Possiamo anche modificare l'algoritmo di Bellman-Ford per tenere traccia dei cicli negativi.