Algorisme de Bellman-Ford

L'algorisme de Bellman-Ford (o algorisme de Bell-End-Ford) genera el camí més curt en un graf dirigit ponderat en què el pes de les arestes pot ser negatiu. L'algorisme de Dijkstra resol aquest mateix problema en un temps menor, però requereix que els pesos de les arestes no siguin negatius. Aquest algorisme va ser desenvolupat per Richard Bellman, Samuel End i Lester Ford.

Segons Robert Sedgewick, "Els pesos negatius no són simplement una curiositat matemàtica; [...] sorgeixen d'una manera natural en la reducció a problemes de camins més curts", i són un exemple d'una reducció del problema del camí hamiltonià que és NP-complet fins al problema de camins més curts amb pesos generals. Si un graf conté un cicle de cost total negatiu llavors aquest graf no té solució. L'algorisme és capaç de detectar aquest cas.

Si el graf conté un cicle de cost negatiu, l'algorisme ho detectés, però no trobarà el camí més curt que no repeteix cap vèrtex. La complexitat d'aquest problema és almenys la del problema del camí més llarg de complexitat NP-Complet.

Algorisme

L'algorisme de Bellman-Ford és, en la seva estructura bàsica, molt semblant a l'algorisme de Dijkstra, però en comptes de seleccionar voraçment el node de pes mínim fins i tot sense processar per relaxar-se, simplement relaxa totes les arestes, i ho fa |V|-1 vegades, sent |V| el nombre de vèrtexs al graf. Les repeticions permeten a les distàncies mínimes recórrer l'arbre, ja que en l'absència de cicles negatius, el camí més curt només visita cada vèrtex una vegada. A diferència de la solució voraç, la qual depèn de la suposició que els pesos siguin positius, aquesta solució s'aproxima més al cas general.

Hi ha dues versions:

Versió no optimitzada per grafs amb cicles negatius, el cost de temps és O(VE).
Versió optimitzada per grafs amb arestes de pes negatiu, però en el graf no hi ha cicles de cost negatiu, el cost de temps, és també O(VE).

 BellmanFord (Graf G, node_origen s) 
// inicialitzar el graf. Posem distàncies a INFINIT menys el node origen que 
// té distància 0
For  v ∈ V [G]  do 
distància [v] = INFINIT
predecessor [v] = NIL

distància [s] = 0

// relaxem cada aresta del graf tantes vegades com nombre de nodes -1 hi hagi al graf 
For  i = 1  to |V [G] -1| do 
For  (u, v) ∈ E [G]  do 
If  distància [v] > distància [u] + pes (u, v)  then 
distància [v] = distància [u] + pes (u, v)
predecessor [v] = u

// comprovem si hi ha cicles negatius 
 For  (u, v) ∈ E [G]  do 
If  distància [v] > distància [u] + pes (u, v) then
print ("Hi ha cicle negatiu")
 Return  FALSE
 Return  TRUE

 BellmanFord_Optimitzat (Graf G, node_origen s) 
// inicialitzar el graf. Posem distàncies a INFINIT menys el node origen que 
// té distància 0. Per això ho fem recorrent tots els vèrtexs del graf 
 For  v ∈ V [G]  do 
distància [v] = INFINIT
pare [v] = NIL
distància [s] = 0
encuar (s, Q)
encuat [s] = TRUE
Mentre  Q ! = 0  then 
u = extreure (Q)
encuat [u] = FALSE
// relaxem les arestes 
For  v ∈ adj [u]  do 
If  distància [v] > distància [u] + pes (u, v)  then 
distància [v] = distància [u] + pes (u, v)
pare [v] = u
If  encuat [v] == FALSE  then 
encuar (v, Q)
encuat [v] = TRUE

Demostració de la correcció de l'algorisme

La correcció de l'algorisme es pot demostrar per inducció. La demostració és la següent:

Lema. Després i repeticions del bucle for:

Si distància (o) no és infinita, llavors és igual a la longitud d'algun camí de s fins u.
Si hi ha un camí des s fins o amb almenys i arestes, aleshores distància (o) és com a màxim la longitud del camí més curt des s a u amb i arestes com a màxim.

Demostració. Per al cas base de la inducció, considerem i = 0 i just abans el bucle for és executat per primera vegada. Després, per al vèrtex origen distància (origen) = 0, el que és cert. Per a qualsevol altre vèrtex o distància (u) = INFINIT, la qual cosa és també correcte perquè no hi ha camí des d'origen fins o amb 0 arestes.

Per al cas inductiu, primer demostrem la primera part. Considerant un moment en què la distància fins al vèrtex és actualitzada per distància (u) = distància (o)+pes (uv). Per la hipòtesi d'inducció, distància (o) és la longitud d'algun camí des d'origen fins u. Llavors distància (o)+pes (uv) és la longitud del camí des de l'origen fins v que segueix el camí des d'origen fins ui després va a v.

Per a la segona part, prenem el camí més curt des d'origen fins o amb almenys i arestes. Deixem av ser l'últim vèrtex abans de o en el seu camí. Després, la part del camí des d'origen fins v és el camí més curt des d'origen fins v amb almenys i-1 arestes. Per la hipòtesi d'inducció, distància(v) després d'i-1 iteracions és a màxim la longitud del seu camí. Llavors, pes(uv)+distància(v) és com a màxim la longitud del camí des de s fins a u. En el primer cicle, distància(o) és comparada amb pes(uv)+distància(v), i és igual a ell si pes(uv)+distància(v) era menor. Llavors, després i iteracions, distància(o) és com a màxim la longitud del camí més curt des d'origen fins o que utilitza com a mínim i arestes.

Si no hi ha cicles de pes negatiu, llavors cada camí més curt visita cada vèrtex com a mínim una vegada, de manera que al pas 3 no se li poden afegir millores. Per contra, suposem que no es pot fer cap canvi. Llavors per a qualsevol vèrtex v [0],.., v [k-1], Distància (v [i]) ≤ Distància (v [i-1 (mod k)])+pes (v [i-1 (mod k)] v [i])

Simplificant, distància (v [i]) i distància (v [i-1 (mod k)]) es cancel·len, deixant:

0\leq \sum _{i=1}^{k}pes(v[i-1(modk)]v[i])

És a dir, cada cicle té pesos no negatius.

Aplicacions d'encaminament

Una variant distribuïda de l'Algorisme de Bellman-Ford s'usa en protocols d'encaminament basats en vector de distàncies, per exemple el Protocol d'encaminament d'informació (RIP). L'algorisme és distribuït perquè envolta una sèrie de nodes (routers) dins d'un Sistema autònom (AS), un conjunt de xarxes i dispositius router IP administrats típicament per un Proveïdor de Servei d'Internet (ISP). Es compon dels següents passos:

Cada node calcula la distància entre ell mateix i tots els altres dins d'un AS i emmagatzema aquesta informació en una taula.
Cada node envia el seu taula a tots els nodes veïns.
Quan un node rep les taules de distàncies dels seus veïns, aquest calcula la ruta més curta als altres nodes i actualitza la seva taula per reflectir els canvis.

Els desavantatges principals de l'algorisme de Bellman-Ford a aquest ajust són:

No escala bé
Els canvis en la topologia de xarxa no es reflecteixen ràpidament, ja que les actualitzacions es distribueixen node per node.
Comptant fins a l'infinit (si una fallada d'enllaç o node fa que un node sigui inabastable des d'un conjunt d'altres nodes, aquests poden estar sempre augmentant gradualment els seus càlculs de distància a ell, i mentrestant pot haver bucles d'encaminament)

Millores

El 1970 Ien va descriure una millora de l'algorisme Bellman-Ford per a un graf sense cicles amb pes negatiu. Aquesta millora primer assigna un ordre arbitrari lineal a tots els vèrtexs i després divideix el conjunt de totes les arestes en un o dos subconjunts. El primer subconjunt, E_f, conté totes les arestes (v_i, v_j) tals que i<j, mentre que el segon, E_b, conté arestes (v_i, v_j) tals que i>j. Cada vèrtex es visita amb vista v₁, v₂, ..., v_|v|, relaxant cada aresta sortint d'aquest vèrtex a E_f. Cada vèrtex és, després, visitat amb vista v_|v|, v_|v|, ..., v₁, relaxant cada aresta sortint d'aquest vèrtex a E_b. La millora de Ien redueix a la meitat, de manera efectiva, el nombre de passos requerits per a la solució del camí més curt des d'una única font.

Vegeu també

Cerca en amplada

Bibliografia

Richard Bellman: On a Routing Problem , in Quarterly of Applied Mathematics, 16 (1), pp.87-90, 1958.
Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks , Princeton University Press, 1962.
Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24/1: The Bellman-Ford algorithm, pp.588-592.