algorithm
Algoritmo di Bellman-Ford
Ricerca…
Osservazioni
Dato un grafico diretto G , spesso vogliamo trovare la distanza più breve da un dato nodo A al resto dei nodi nel grafico. L' algoritmo Dijkstra è l'algoritmo più famoso per trovare il percorso più breve, tuttavia funziona solo se i pesi degli spigoli del grafico dato sono non negativi. Tuttavia, Bellman-Ford mira a trovare il percorso più breve da un dato nodo (se ne esiste uno) anche se alcuni pesi sono negativi. Si noti che la distanza più breve potrebbe non esistere se nel grafico è presente un ciclo negativo (nel qual caso si può aggirare il ciclo risultante in una distanza totale infinitamente piccola). Bellman-Ford ci consente inoltre di determinare la presenza di un tale ciclo.
La complessità totale dell'algoritmo è O(V*E) , dove V - è il numero di vertici e il numero E di spigoli
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:
- d [4] + costo [4] [5] = infinito + 7 = infinito . Non possiamo aggiornare questo.
- d [2] + costo [3] [4] = infinito . Non possiamo aggiornare questo.
- d [1] + costo [1] [2] = 0 + 2 = 2 < d [2] . Quindi d [2] = 2 . Anche genitore [2] = 1 .
- d [1] + costo [1] [4] = 4 . Quindi d [4] = 4 < d [4] . genitore [4] = 1 .
- d [4] + costo [4] [6] = 9 . d [6] = 9 < d [6] . genitore [6] = 4 .
- 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:
- d [4] + costo [4] [5] = 12 < d [5] . d [5] = 12 . genitore [5] = 4 .
- d [3] + costo [3] [4] = 1 < d [4] . d [4] = 1 . genitore [4] = 3 .
- d [3] rimane invariato.
- d [4] rimane invariato.
- d [4] + costo [4] [6] = 6 < d [6] . d [6] = 6 . genitore [6] = 4 .
- 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:
- d [3] + costo [3] [4] = infinito . Non cambierà nulla.
- d [2] + costo [2] [3] = infinito . Non cambierà nulla.
- 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:
- d [3] + costo [3] [4] = infinito . Non cambierà nulla.
- d [2] + costo [2] [3] = 5 < d [3] . d [3] = 5 . genitore [3] = 2.
- Non sarà cambiato.
Questa volta il processo di rilassamento è cambiato d [3] . Il nostro grafico sarà simile a: 
Terza iterazione:
- d [3] + costo [3] [4] = 7 < d [4] . d [4] = 7 . genitore [4] = 3 .
- Non sarà cambiato.
- 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:
- d [1] + costo [1] [2] = 2 < d [2] . d [2] = 2 .
- d [2] + costo [2] [3] = 5 < d [3] . d [3] = 5 .
- 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.
