algorithm
Algoritmo de Bellman-Ford

Observaciones

Algoritmo de ruta más corta de una sola fuente (dado que hay un ciclo negativo en una gráfica)

Antes de leer este ejemplo, se requiere tener una breve idea sobre la relajación del borde. Puedes aprenderlo desde aquí.

El algoritmo de Bellman-Ford calcula las rutas más cortas desde un solo vértice fuente a todos los otros vértices en un dígrafo ponderado. Aunque es más lento que el algoritmo de Dijkstra , funciona en los casos en que el peso del borde es negativo y también encuentra un ciclo de peso negativo en la gráfica. El problema con el algoritmo de Dijkstra es que, si hay un ciclo negativo, sigues repitiendo el ciclo una y otra vez y continúas reduciendo la distancia entre dos vértices.

La idea de este algoritmo es recorrer todos los bordes de este gráfico uno por uno en un orden aleatorio. Puede ser cualquier orden aleatorio. Pero debe asegurarse de que si uv (uno de los vértices de u y v son dos vértices en una gráfica) es uno de sus pedidos, entonces debe haber un margen de u a v . Por lo general, se toma directamente del orden de la entrada dada. De nuevo, cualquier orden aleatorio funcionará.

Después de seleccionar el orden, relajaremos los bordes según la fórmula de relajación. Para un borde dado uv que va de u a v, la fórmula de relajación es:

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

Es decir, si la distancia de la fuente a cualquier vértice u + el peso del borde uv es menor que la distancia de la fuente a otro vértice v , actualizamos la distancia de la fuente a v . Necesitamos relajar los bordes como máximo (V-1) donde V es el número de bordes en el gráfico. ¿Por qué (V-1) preguntas? Lo explicaremos en otro ejemplo. También vamos a hacer un seguimiento del vértice padre de cualquier vértice, es decir, cuando relajamos un borde, estableceremos:

parent[v] = u

Significa que hemos encontrado otro camino más corto para alcanzar v a través de u . Necesitaremos esto más adelante para imprimir la ruta más corta desde la fuente hasta el vértice destinado.

Veamos un ejemplo. Tenemos un gráfico:

Hemos seleccionado 1 como el vértice de origen . Queremos encontrar la ruta más corta desde la fuente a todos los demás vértices.

Al principio, d [1] = 0 porque es la fuente. Y el descanso es infinito , porque aún no sabemos su distancia.

Vamos a relajar los bordes en esta secuencia:

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

Puedes tomar cualquier secuencia que quieras. Si relajamos los bordes una vez, ¿qué obtenemos? Obtenemos la distancia desde la fuente a todos los otros vértices de la ruta que utiliza a lo sumo 1 borde. Ahora relajemos los bordes y actualicemos los valores de d [] . Obtenemos:

1. d [4] + costo [4] [5] = infinito + 7 = infinito . No podemos actualizar este.
2. d [2] + costo [3] [4] = infinito . No podemos actualizar este.
3. d [1] + costo [1] [2] = 0 + 2 = 2 < d [2] . Entonces d [2] = 2 . También padre [2] = 1 .
4. d [1] + costo [1] [4] = 4 . Entonces d [4] = 4 < d [4] . padre [4] = 1 .
5. d [4] + costo [4] [6] = 9 . d [6] = 9 < d [6] . padre [6] = 4 .
6. d [2] + costo [2] [2] = infinito . No podemos actualizar este.

No pudimos actualizar algunos vértices, porque la condición d[u] + cost[u][v] < d[v] no coincidió. Como hemos dicho anteriormente, encontramos las rutas desde la fuente a otros nodos utilizando un máximo de 1 borde.

Nuestra segunda iteración nos proporcionará la ruta utilizando 2 nodos. Obtenemos:

1. d [4] + costo [4] [5] = 12 < d [5] . d [5] = 12 . padre [5] = 4 .
2. d [3] + costo [3] [4] = 1 < d [4] . d [4] = 1 . padre [4] = 3 .
3. d [3] permanece sin cambios.
4. d [4] permanece sin cambios.
5. d [4] + costo [4] [6] = 6 < d [6] . d [6] = 6 . padre [6] = 4 .
6. d [3] permanece sin cambios.

Nuestro gráfico se verá como:

Nuestra tercera iteración solo actualizará el vértice 5 , donde d [5] será 8 . Nuestro gráfico se verá como:

Después de esto, sin importar cuántas iteraciones hagamos, tendremos las mismas distancias. Así que mantendremos una bandera que verifique si alguna actualización tiene lugar o no. Si no es así, simplemente romperemos el bucle. Nuestro pseudo-código será:

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

Para realizar un seguimiento del ciclo negativo, podemos modificar nuestro código mediante el procedimiento descrito aquí . Nuestro pseudo-código completado será:

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

Ruta de impresión:

Para imprimir la ruta más corta a un vértice, volveremos a iterar a su padre hasta que encontremos NULL e imprimamos los vértices. El pseudocódigo será:

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

Complejidad:

Como necesitamos relajar los tiempos máximos de bordes (V-1) , la complejidad del tiempo de este algoritmo será igual a O (V * E) donde E denota el número de bordes, si usamos la adjacency list para representar el gráfico. Sin embargo, si se usa una adjacency matrix para representar el gráfico, la complejidad del tiempo será O (V ^ 3) . La razón es que podemos iterar a través de todos los bordes en el tiempo O (E) cuando se usa la adjacency list , pero toma el tiempo O (V ^ 2) cuando se usa la adjacency matrix .

¿Por qué necesitamos relajar todos los bordes como máximo (V-1) veces?

Para comprender este ejemplo, se recomienda tener una breve idea del algoritmo de ruta más corta de fuente única de Bellman-Ford que se puede encontrar aquí.

En el algoritmo de Bellman-Ford, para descubrir la ruta más corta, necesitamos relajar todos los bordes del gráfico. Este proceso se repite como máximo (V-1) veces, donde V es el número de vértices en el gráfico.

El número de iteraciones necesarias para encontrar la ruta más corta desde la fuente a todos los demás vértices depende del orden que seleccionamos para relajar los bordes.

Echemos un vistazo a un ejemplo:

Aquí, el vértice de origen es 1. Descubriremos la distancia más corta entre el origen y todos los demás vértices. Podemos ver claramente que, para alcanzar el vértice 4 , en el peor de los casos, tomará los bordes (V-1) . Ahora, dependiendo del orden en que se descubren los bordes, puede tomar (V-1) veces descubrir el vértice 4 . ¿No lo conseguiste? Usemos el algoritmo de Bellman-Ford para encontrar el camino más corto aquí:

Vamos a utilizar esta secuencia:

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

Para nuestra primera iteración:

1. d [3] + costo [3] [4] = infinito . No cambiará nada.
2. d [2] + costo [2] [3] = infinito . No cambiará nada.
3. d [1] + costo [1] [2] = 2 < d [2] . d [2] = 2 . padre [2] = 1 .

Podemos ver que nuestro proceso de relajación solo cambió d [2] . Nuestro gráfico se verá como:

Segunda iteración:

1. d [3] + costo [3] [4] = infinito . No cambiará nada.
2. d [2] + costo [2] [3] = 5 < d [3] . d [3] = 5 . padre [3] = 2.
3. No será cambiado.

Esta vez el proceso de relajación cambió d [3] . Nuestro gráfico se verá como:

Tercera iteración:

1. d [3] + costo [3] [4] = 7 < d [4] . d [4] = 7 . padre [4] = 3 .
2. No será cambiado.
3. No será cambiado.

Nuestra tercera iteración finalmente descubrió el camino más corto a 4 de 1 . Nuestro gráfico se verá como:

Entonces, se necesitaron 3 iteraciones para descubrir el camino más corto. Después de este, no importa cuántas veces relajemos los bordes, los valores en d [] seguirán siendo los mismos. Ahora, si consideramos otra secuencia:

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

Nosotros obtendríamos

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 .

Nuestra primera iteración ha encontrado la ruta más corta desde la fuente a todos los demás nodos. Otra secuencia 1-> 2 , 3-> 4 , 2-> 3 es posible, lo que nos dará el camino más corto después de 2 iteraciones. Podemos llegar a la decisión de que, sin importar cómo ordenemos la secuencia, no se necesitarán más de 3 iteraciones para encontrar la ruta más corta desde la fuente en este ejemplo.

Podemos concluir que, en el mejor de los casos, tomará 1 iteración para descubrir la ruta más corta desde la fuente . En el peor de los casos, tomará iteraciones (V-1) , por lo que repetimos el proceso de relajación (V-1) .

Detectando ciclo negativo en una gráfica

Para comprender este ejemplo, se recomienda tener una breve idea sobre el algoritmo de Bellman-Ford que se puede encontrar aquí.

Usando el algoritmo de Bellman-Ford, podemos detectar si hay un ciclo negativo en nuestra gráfica. Sabemos que, para descubrir la ruta más corta, necesitamos relajar todos los bordes del gráfico (V-1) , donde V es el número de vértices en un gráfico. Ya hemos visto que en este ejemplo , después de las iteraciones (V-1) , no podemos actualizar d [] , no importa cuántas iteraciones hagamos. ¿O podemos?

Si hay un ciclo negativo en una gráfica, incluso después de las iteraciones (V-1) , podemos actualizar d [] . Esto sucede porque para cada iteración, atravesar el ciclo negativo siempre disminuye el costo de la ruta más corta. Esta es la razón por la que el algoritmo de Bellman-Ford limita el número de iteraciones a (V-1) . Si usáramos el algoritmo de Dijkstra aquí, estaríamos atrapados en un bucle sin fin. Sin embargo, concentrémonos en encontrar el ciclo negativo.

Supongamos que tenemos un gráfico:

Vamos a elegir el vértice 1 como la fuente . Después de aplicar el algoritmo de ruta más corta de una sola fuente de Bellman-Ford al gráfico, descubriremos las distancias desde la fuente a todos los otros vértices.

Así es como se ve la gráfica después de (V-1) = 3 iteraciones. Debería ser el resultado ya que hay 4 bordes, necesitamos como máximo 3 iteraciones para encontrar el camino más corto. Entonces, o esta es la respuesta, o hay un ciclo de peso negativo en la gráfica. Para encontrar eso, después de las iteraciones (V-1) , hacemos una iteración final más y si la distancia continúa disminuyendo, significa que definitivamente hay un ciclo de peso negativo en la gráfica.

Para este ejemplo: si marcamos 2-3 , d [2] + costo [2] [3] nos dará 1 que es menor que d [3] . Entonces podemos concluir que hay un ciclo negativo en nuestra gráfica.

Entonces, ¿cómo averiguamos el ciclo negativo? Hacemos una pequeña modificación al procedimiento de 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"

Así es como descubrimos si hay un ciclo negativo en una gráfica. También podemos modificar el algoritmo de Bellman-Ford para realizar un seguimiento de los ciclos negativos.