Bellman-Ford Algorithm

Uno de los algoritmos indicados para resolver el problema de los caminos mas cortos desde una fuente a múltiples destinos, podría ser el de Bellman-Ford. A diferencia del algoritmo de Dijkstra, Bellman-Ford puede ser aplicado en grafos con ciclos negativos.  Generalmente, este algoritmo encuentra los caminos mas cortos de una fuente $s \in V$ para todo $v \in V$ en un grafo $G(V,E)$ o determina que existe un ciclo de peso negativo alcanzable por la fuente.

Si un grafo $G(V,E)$ contiene un ciclo de peso de negativo entoces el camino mas corto no existe.

Veamos lo siguiente...

Supóngase que tenemos el siguiente grafo. 

Este grafo contiene un ciclo $c=<u,r,u>$ donde su peso  es $w(c)=w(u,r)+w(r,u)=-2\leq0$ es negativo, ademas de esto es alcanzable por la fuente $s$. Si tomamos el siguiente camino  $p=<s,u,r,u,v>$ para llegar a $v$ este seria un camino de peso $w(p)=1$, sin embargo como $c$ es un ciclo, si tomamos el siguiente camino $p_{1}=<s,u,r,u,r,u,v>$ entonces el nuevo peso es $w(p_{1})=-1$, si $p_{2}=<s,u,r,u,r,u,r,u,v>$ tendremos que su peso es igual a $-3$ y así sucesivamente si vamos tomando nuevos camino por el ciclo podemos hallar siempre un camino mas corto hacia $v$ hasta $-\infty$, lo que causa que este no exista.

El siguiente código muestra el algoritmo de Bellman-Ford.

Ahora para el grafo dado en la figura de abajo, tenemos la siguiente tabla, que muestra la corrida del algoritmo.

La ultima iteración muestra el tamaño del camino mas corto para llegar de $s$ a los demás vértices, teniendo en cuenta el orden de las aristas anterior. 

Cabe aclarar que este orden es arbitrario y podemos tomar el que mas nos crea conveniente.

El siguiente teorema muestra que Bellman-Ford corre correctamente.

Primero veamos los siguientes lemas.

Lema1

 Sea $s \rightsquigarrow u \rightarrow v $es un camino mas corto y si $d[u]=\delta(s,u)$ entonces $d[v]=\delta(s,v)$ después de la relajación.

Lema

Si $G(V,E)$ no contiene ciclos negativos alcanzables por $s$. Entonces en la terminación de Bellman-Ford $d[v]=\delta(s,v)$ para todo $v$ alcanzable por $s$.

Prueba

Sea $v$ un vértice alcanzable por $s$, sea $p=<v_{0},...,v_{k}>$ un camino mas corto de $s$ a $v$ donde $v_{0}=s$ y $v_{k}=v$ y tiene el menor numero de aristas posibles. (p es un camino simple sin ciclos, es decir no se repiten vértices).

Inducción

• $d[v_{0}]=0=\delta(s,v_{0})=\delta(s,s)=0$ después de la inicialización esta igualdad se mantiene.
• (Hipótesis de inducción): $d[v_{i-1}]=\delta(s,v_{i-1})$ después de $i-1$ pasos.
• Veamos que $d[v_{i}]=\delta(s,v_{i})$ si aplicamos el método RELAX a la arista $(v_{i-1},v_{i})$ en el paso $i$ entonces como $p$ es un camino mas corto y el lema1, $d[v_{i}]=\delta(s,v_{i})$ 

Teorema

Supongamos que $G$ no contiene ciclos de peso negativo. Entonces por el lema anterior $d[v]=\delta(s,v)$ entonces veamos que el algoritmo de Bellman-Ford retorna ''true".  Y si $G$ tiene algún ciclo negativo entonces retorna ''false''.

 

Prueba

En la terminación $d[v]=\delta(s,v)\leq\delta(s,u)+w(u,v)=d[u]+w(u,v)$ por desigualdad triangular y lema anterior.

Ahora por lo anterior tenemos que $d[v]\leqd[u]+w(u,v)$ para cada arista $(u,v)$ en $E$ esto muestra que la linea $6$ del algoritmo falla, luego retorna ''true''.

Ahora para la segunda parte, tenemos que $G$ contiene un ciclo negativo digamos $c=<v_{0},...,v_{k}>$ donde $v_{0}=v_{k}$ alcanzable por $s$, entonces $\sum_{i=1}^{k}w(v_{i-1},v_{i})<0$. Supóngase que Bellman-Ford retorna ''true" Esto es $d[v_{i}]\leqd[v_{i-1}]+w(v_{i-1},v_{i})$ para $i=1,...,k.$

Entonces $$\sum_{i=1}^{k}d[v_{i}]\leq\sum_{i=1}^{k}d[v_{i-1}]+\sum_{i=1}^{k}w(v_{i-1},v_{i})$$ 

Luego como $\sum_{i=1}^{k}d[v_{i}]=\sum_{i=1}^{k}d[v_{i-1}]$ porque cada vértice aparece una sola vez en cada ciclo de cada suma.

Por tanto $0\leq\sum_{i=1}^{k}w(v_{i-1},v_{i})$ pero esto contradice que el ciclo sea de peso negativo mostrado anteriormente. Luego retorna '''false'.

Nos vemos en otra ocasión.