Anar al contingut

Algoritme de Bellman-Ford

De L'Enciclopèdia, la wikipedia en valencià
Algoritme de Bellman-Ford
En esta taula es mostren les solucions parcials que s'han anat obtenint per mig de la realisació de l'algoritme. Un eixemple de la resolució final de l'algoritme.

L'algoritme de Bellman-Ford genera el camí més curt en un grafo dirigit ponderat (en el que el pes d'alguna de les arestes pot ser negatiu). l'algoritme de Dijkstra resol este mateix problema en un temps menor, pero requerix que els pesos de les arestes no siguen negatius, llevat que el grafo siga dirigit i sense cicles. Per lo que l'Algoritme Bellman-Ford normalment s'utilisa quan hi ha arestes en pes negatiu. Este algoritme va ser desenrollat per Richard Bellman, Samuel End i Lester Ford.

Segons Robert Sedgewick, “Els pesos negatius no són simplement una curiositat matemàtica; […] sorgixen d'una forma natural en la reducció a problemes de camins més curts”, i són un eixemple d'una reducció del problema del camí hamiltoniano que és NP-complet fins al problema de camins més curts en pesos generals. Si un grafo conté un cicle de cost total negatiu llavors este grafo no té solució. L'algoritme és capaç de detectar este cas.

Si el grafo conté un cicle de cost negatiu, l'algoritme ho detectarà, pero no trobarà el camí més curt que no repetix cap vèrtiç. La complexitat d'este problema és a lo manco la del problema del camí més llarc de complexitat NP-Complet.

Algoritme

L'Algoritme de Bellman-Ford és, en la seua estructura bàsica, molt semblat a l'algoritme de Dijkstra, pero en lloc de seleccionar vorazmente el nodo de pes mínim encara sense processar per a relaixar-ho, simplement relaixa totes les arestes, i ho fa |V|-1 voltes, sent |V| el número de vèrtiços en el grafo. Les repeticions permeten a les distàncies mínimes recórrer l'arbre, ya que en l'absència de cicles negatius, el camí més curt solament visita cada vèrtiç una volta. A diferència de la solució voraç, la qual depén de la suposició de que els pesos siguen positius, esta solució s'aproxima més al cas general.

Existixen dos versions:

  • Versió no optimisada per a grafos en cicles negatius, el cost dels quals de temps és O(VE).
  • Versió optimisada per a grafos en arestes de pes negatiu, pero en el grafo no existixen cicles de cost negatiu, el cost del qual de temps, és també O(VE).
   bool BellmanFord(Grafo G, nodo_orige s)
      // inicializamos el grafo. Posem distàncies a INFINITO menys el nodo orige que 
      // té distància 0
       for v ∈ V[G] do
           distancia[v]=INFINITO
           predecessor[v]=NULL
       distància[s]=0
       // relaixem cada aresta del grafo tantes voltes com a número de nodos -1 hi haja en el grafo
       for i=1 to |V[G]|-1 do
           for (o, v) ∈ I[G] do
               if distància[v]>distància[o] + pes(o, v) then
                   distància[v] = distància[o] + pes (o, v)
                   predecessor[v] = o
       // comprovem si hi ha cicles negatiu
       for (o, v) ∈ I[G] do
           if distància[v] > distància[o] + pes(o, v) then
               print ("Hi ha cicle negatiu")
               return FALSE
       return TRUE

  bool BellmanFord_Optimisat(Grafo G, nodo_orige s)
       // inicializamos el grafo. Posem distàncies a INFINITO menys el nodo orige que
       // té distància 0. Per a això ho fem recorrent-nos tots els vèrtiços del grafo
       for v ∈ V[G] do
           distancia[v]=INFINITO
           pare[v]=NULL
       distància[s]=0
       encolar(s, Q)
       en_coa[s]=TRUE
       while Q!=0 then
           o = extraure(Q)
           en_coa[o]=FALSE
           // relaixem les arestes
           for v ∈ ady[o] do
               if distància[v]>distància[o] + pes(o, v) then
                   distància[v] = distància[o] + pes (o, v)
                   pare[v] = o
                   if en_coa[v]==FALSE then
                       encolar(v, Q)

en_coa[v]=TRUE

Aplicacions de enrutamiento

Una variant distribuïda de l'Algoritme del Bellman-Ford s'usa en protocols d'encaminada basats en vector de distàncies, per eixemple el Protocol d'encaminada d'informació (RIP). L'algoritme és distribuït perque envol una série de nodos (routers) dins d'un Sistema autònom(AS), un conjunt de rets i dispositius router IP administrats típicament per un Proveïdor de Servici d'Internet (ISP). Es compon dels següents passos:

  1. Cada nodo calcula la distància entre ell mateix i tots els demés dins d'un AS i almagasena esta informació en una taula.
  2. Cada nodo envia la seua taula a tots els nodos veïns.
  3. Quan un nodo rep les taules de distàncies dels seus veïns, est calcula la ruta més curta als demés nodos i actualisa la seua taula per a reflectir els canvis.

Les desventages principals de l'algoritme de Bellman-Ford en este ajust són:

  • No escala be
  • Els canvis en la topología de ret no es reflectixen ràpidament ya que les actualisacions es distribuïxen nodo per nodo.
  • Contant fins a l'infinit(si un fallo d'enllaç o nodo fa que un nodo siga inalcançable des d'un conjunt d'atres nodos, estos poden estar sempre aumentant gradualment els seus càlculs de distància a ell, i mentrestant pot haver bucles de enrutamiento)

Millores

En 1970 Yen va descriure una millora de l'algoritme Bellman-Ford per a un grafo sense cicles en pes negatiu. Esta millora primer assigna un orde arbitrari llineal a tots els vèrtiços i despuix dividix el conjunt de totes les arestes en un o dos subconjunts. El primer subconjunt, If, conté totes les arestes (vi,vj) tals que i < j; mentres que el segon, Ib, conté arestes (vi,vj) tals que i > j. Cada vèrtiç es visita en orde v1,v2,…,v|v|, relaixant cada aresta eixint d'eixe vèrtiç en If. Cada vèrtiç és, despuix, visitat en orde v|v|,v|v-1|,…,v1, relaixant cada aresta eixint d'eixe vèrtiç en Ib. La millora de Yen reduïx a la mitat, de manera efectiva, el número de “passes” requerits per a la solució del camí més curt des d'una única font.

Vore també

Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Algoritme_de_Bellman-Ford&oldid=1589558»