CAMINO MAS CORTO: ALGORITMO DE BELLMAN-FORD
Enviado por olga_sh • 26 de Enero de 2016 • Apuntes • 10.848 Palabras (44 Páginas) • 651 Visitas
CAMINO MAS CORTO: ALGORITMO DE BELLMAN-FORD
Publicado el enero 1, 2013| 4 comentarios
En esta oportunidad se explicará el algoritmo de Bellman-Ford para hallar la ruta más corta, comenzaremos con una breve introducción al problema de hallar la ruta más corta sobre pesos negativos y luego continuaremos con el algoritmo de Bellman-ford.
Algoritmo de Dijkstra y Pesos Negativos
Si el grafo posee pesos negativos, el algoritmo de Dijkstra puede producir respuestas incorrectas. Por ejemplo tengamos el siguiente grafo:
[pic 1]
Si deseo la ruta más corta partiendo desde el vértice 1 según dijkstra la ruta más corte de vértice 1 al vértice 3 sería 2. Sin embargo la ruta más corta en realidad es de 1 (1 -> 2 -> 4 ->3).
Ciclos Negativos
Cuando consideremos pesos negativos en las aristas, al momento de hallar la ruta más corta, es posible que se generen ciclos. Veamos el siguiente ejemplo:
[pic 2]
Tratemos de hallar la ruta más corta aplicando Dijkstra desde el vértice 1:
[pic 3]
Partimos de vértice 1 con peso igual a 0 y actualizamos peso de vértice 2:
[pic 4]
Ahora actualizamos peso de vértice 3:
[pic 5]
Según el algoritmo descrito en CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA. El algoritmo terminaría, eso se da debido a que estábamos usando una arreglo de visitados de esta manera no caería en ciclos negativos; sin embargo la solución no sería correcta. Si omitimos el arreglo de visitados para hallar la ruta más corta, el algoritmo caería en un ciclo:
[pic 6]
Como se puede ver en la figura, tenemos un ciclo negativo ya que siempre encontrará una mejor ruta entre los vértices 2 y 3.
Algoritmo de Bellman-Ford
Descripción
El algoritmo de Bellman-Ford determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. La diferencia de este algoritmo con los demás es que los pesos pueden tener valores negativos ya que Bellman-Ford me permite detectar la existencia de un ciclo negativo.
Como trabaja
El algoritmo parte de un vértice origen que será ingresado, a diferencia de Dijkstra que utiliza una técnica voraz para seleccionar vértices de menor peso y actualizar sus distancias mediante el paso de relajación, Bellman-Ford simplemente relaja todas las aristas y lo hace |V| – 1 veces, siendo |V| el número de vértices del grafo.
Para la detección de ciclos negativos realizamos el paso de relajación una vez más y si se obtuvieron mejores resultados es porque existe un ciclo negativo, para verificar porque tenemos un ciclo podemos seguir relajando las veces que queramos y seguiremos obteniendo mejores resultados.
Algoritmo en pseudocódigo
Considerar distancia[ i ] como la distancia más corta del vértice origen ingresado al vértice i y |V| el número de vértices del grafo.
1 método BellmanFord(Grafo,origen):
2 inicializamos las distancias con un valor grande
3 distancia[ origen ] = 0
4 para i = 1 hasta |V| - 1:
5 para cada arista E del Grafo:
6 sea ( u , v ) vértices que unen la arista E
7 sea w el peso entre vértices ( u , v )
8 Relajacion( u , v , w )
9 para cada arista E del Grafo:
10 sea ( u , v ) vértices que unen la arista E
11 sea w el peso entre vértices ( u , v )
12 si Relajacion( u , v , w )
13 Imprimir “Existe ciclo negativo”
15 Terminar Algoritmo
1 Relajacion( actual , adyacente , peso ):
2 si distancia[ actual ] + peso < distancia[ adyacente ]
3 distancia[ adyacente ] = distancia[ actual ] + peso
Ejemplo y Código paso a paso
Tengamos el siguiente grafo, cuyos ID están en color negro encima de cada vértice, los pesos esta en color azul y la distancia inicial en cada vértice es infinito
[pic 7]
Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.
1 2 3 | #define MAX 105 //maximo numero de vértices #define Node pair< int , int > //definimos el nodo como un par( first , second ) donde first es el vertice adyacente y second el peso de la arista #define INF 1<<30 //definimos un valor grande que represente la distancia infinita inicial, basta conque sea superior al maximo valor del peso en alguna de las aristas |
Inicializamos los valores de nuestros arreglos:
[pic 8]
Dónde:
- Vértices: ID de los vértices.
- Distancia[ u ]: Distancia más corta desde vértice inicial a vértice con ID = u.
- Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, me servirá para impresión del camino más corto.
En cuanto al código los declaramos de la siguiente manera:
1 2 3 4 | vector< Node > ady[ MAX ]; //lista de adyacencia int distancia[ MAX ]; //distancia[ u ] distancia de vértice inicial a vértice con ID = u int previo[ MAX ]; //para la impresion de caminos int V; //numero de vertices |
Y la función de inicialización será simplemente lo siguiente:
...