Ejercicio Grafo

La ruta mas corta

La ruta mas corta

CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA

Publicado el marzo 19, 2012| 60 comentarios

Para el problema de la ruta corta tenemos varios algoritmos, en esta oportunidad se explicará el algoritmo de dijkstra el cual usa una técnica voraz (greedy). Al final del articulo se encuentran adjuntas las implementaciones en C++ y JAVA.

Descripción

El algoritmo de dijkstra 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. Algunas consideraciones:

• Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
• Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Como trabaja

Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy – La técnica greedy utiliza el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).

Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos.

Tanto java como C++ cuentan con una cola de prioridad ambos implementan un Binary Heap aunque con un Fibonacci Heap la complejidad de dijkstra se reduce haciéndolo mas eficiente, pero en un concurso mas vale usar la librería que intentar programar una nueva estructura como un Fibonacci Heap, claro que particularmente uno puede investigar y programarlo para saber como funciona internamente.

Algoritmo en pseudocódigo

Considerar distancia[ i ] como la distancia mas corta del vértice origen ingresado al vértice i.

1  método Dijkstra(Grafo,origen):
2      creamos una cola de prioridad Q
3      agregamos origen a la cola de prioridad Q
4      mientras Q no este vacío:
5          sacamos un elemento de la cola Q llamado u
6          si u ya fue visitado continuo sacando elementos de Q    
7          marcamos como visitado u
8          para cada vértice v adyacente a u en el Grafo:
9              sea w el peso entre vértices ( u , v )  
10             si v no ah sido visitado:
11                Relajacion( u , v , w )

1  método Relajacion( actual , adyacente , peso ):
2      si distancia[ actual ] + peso < distancia[ adyacente ]
3         distancia[ adyacente ] = distancia[ actual ] + peso
4         agregamos adyacente a la cola de prioridad Q

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

Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.

1 2 3

#define MAX 10005 //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

Donde:

• Vértices: ID de los vértices.
• Distancia[ u ]: Distancia mas corta desde vértice inicial a vértice con ID = u.
• Visitado[ u ]: 0 si el vértice con ID = u no fue visitado y 1 si ya fue visitado.
• Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, me servirá para impresión del camino mas corto.

En cuanto al código los declaramos de la siguiente manera:

1 2 3 4 5 6

vector< Node > ady[ MAX ]; //lista de adyacencia int distancia[ MAX ];      //distancia[ u ] distancia de vértice inicial a vértice con ID = u bool visitado[ MAX ];      //para vértices visitados int previo[ MAX ];         //para la impresion de caminos priority_queue< Node , vector<Node> , cmp > Q; //priority queue propia del c++, usamos el comparador definido para que el de menor valor este en el tope int V;                     //numero de vertices

Y la función de inicialización será simplemente lo siguiente

1 2 3 4 5 6 7 8

//función de inicialización void init(){     for( int i = 0 ; i <= V ; ++i ){         distancia[ i ] = INF;  //inicializamos todas las distancias con valor infinito         visitado[ i ] = false; //inicializamos todos los vértices como no visitado         previo[ i ] = -1;      //inicializamos el previo del vértice i con -1     } }

De acuerdo al vértice inicial que elijamos cambiara la distancia inicial, por ejemplo la ruta más corta partiendo del vértice 1 a todos los demás vértices:

El vértice 1 es visitado, la distancia de vértice 1 -> vértice 1 es 0 por estar en el mismo lugar.

1 2	Q.push( Node( inicial , 0 ) ); //Insertamos el vértice inicial en la Cola de Prioridad distancia[ inicial ] = 0;      //Este paso es importante, inicializamos la distancia del inicial como 0

Extraemos el tope de la cola de prioridad

1 2 3

while( !Q.empty() ){                   //Mientras cola no este vacia         actual = Q.top().first;            //Obtengo de la cola el nodo con menor peso, en un comienzo será el inicial         Q.pop();                           //Sacamos el elemento de la cola

Si el tope ya fue visitado entonces no  tengo necesidad de evaluarlo, por ello continuaría extrayendo elementos dela cola:

1	if( visitado[ actual ] ) continue; //Si el vértice actual ya fue visitado entonces sigo sacando elementos de la cola

En este caso al ser el tope el inicial no esta visitado por lo tanto marcamos como visitado.

1	visitado[ actual ] = true;         //Marco como visitado el vértice actual

Hasta este momento la tabla quedaría de la siguiente manera

Ahora vemos sus adyacentes que no hayan sido visitados. Tendríamos 2 y 4.

1 2 3 4

for( int i = 0 ; i < ady[ actual ].size() ; ++i ){ //reviso sus adyacentes del vertice actual     adyacente = ady[ actual ][ i ].first;   //id del vertice adyacente     peso = ady[ actual ][ i ].second;        //peso de la arista que une actual con adyacente ( actual , adyacente )     if( !visitado[ adyacente ] ){        //si el vertice adyacente no fue visitado

Evaluamos primero para vértice 2

Vemos que la distancia actual desde el vértice inicial a 2 es ∞, verifiquemos el paso de relajación:

distancia[ 1 ] + 7 < distancia[ 2 ]      ->       0 + 7 < ∞        ->         7 < ∞

El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 2 y agregando el vértice en la cola de prioridad con nueva distancia quedando:

El paso de relajación se daría en la siguiente parte:

1 2 3 4 5 6 7

for( int i = 0 ; i < ady[ actual ].size() ; ++i ){ //reviso sus adyacentes del vertice actual     adyacente = ady[ actual ][ i ].first;   //id del vertice adyacente     peso = ady[ actual ][ i ].second;        //peso de la arista que une actual con adyacente ( actual , adyacente )     if( !visitado[ adyacente ] ){        //si el vertice adyacente no fue visitado         relajacion( actual , adyacente , peso ); //realizamos el paso de relajacion     } }

Donde la función de relajación seria

1 2 3 4 5 6 7 8 9

//Paso de relajacion void relajacion( int actual , int adyacente , int peso ){     //Si la distancia del origen al vertice actual + peso de su arista es menor a la distancia del origen al vertice adyacente     if( distancia[ actual ] + peso < distancia[ adyacente ] ){         distancia[ adyacente ] = distancia[ actual ] + peso;  //relajamos el vertice actualizando la distancia         previo[ adyacente ] = actual;                         //a su vez actualizamos el vertice previo         Q.push( Node( adyacente , distancia[ adyacente ] ) ); //agregamos adyacente a la cola de prioridad     } }

Ahora evaluamos al siguiente adyacente que es el vértice 4:

De manera similar al anterior vemos que la distancia actual desde el vértice inicial a 4 es ∞, verifiquemos el paso de relajación:

distancia[ 1 ] + 2 < distancia[ 4 ]      ->      0 + 2 < ∞        ->        2 < ∞

El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 4 quedando:

En cuanto a la cola de prioridad como tenemos un vértice con menor peso este nuevo vértice ira en el tope de la cola:

Revisamos sus adyacentes no visitados que serian vértices 2, 3 y 5.

Empecemos por el vértice 2:

Ahora vemos que la distancia actual del vértice inicial al vértice 2 es 7, verifiquemos el paso de relajación:

distancia[ 4 ] + 3 < distancia[ 2 ]      ->      2 + 3 < 7         ->         5 < 7

En esta oportunidad hemos encontrado una ruta mas corta partiendo desde el vértice inicial al vértice 2, actualizamos la distancia en el vértice 2 y actualizamos el vértice previo al actual quedando:

En cuanto a la cola de prioridad como tenemos un vértice con menor peso este nuevo vértice ira en el tope de la cola, podemos ver que tenemos 2 veces el mismo vértice pero como usamos una técnica greedy siempre usaremos el valor óptimo:

Continuamos con los Vértices 3 y 5 como tienen valor ∞ si será posible relajarlos por lo que sería similar a los pasos iniciales solo que en los pasos iniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2, quedando:

El algoritmo de Dijkstra

El algoritmo de Dijkstra te permite calcular la ruta más corta entre un nodo (tú eliges cuál) y todos los demás nodos en el grafo. Encontrarás una descripción del algoritmo al final de esta página, pero ¡vamos a estudiarlo con un ejemplo explicado! Calcularemos la distancia más corta entre el nodo C y los demás nodos del grafo:

Durante la ejecución del algoritmo, iremos marcando cada nodo con su distancia mínima al nodo C (nuestro nodo elegido). Para el nodo C, esta distancia es 0. Para el resto de nodos, como todavía no conocemos esa distancia mínima, empieza siendo infinita (∞):

También tendremos un nodo actual. Inicialmente, el nodo actual será C (nuestro nodo elegido). En la imagen, marcaremos el nodo actual con un punto rojo.

Ahora, revisaremos los vecinos de nuestro nodo actual (A, B y D) en cualquier orden. Empecemos con B. Sumamos la mínima distancia del nodo actual (en este caso, 0) con el peso de la arista que conecta al nodo actual con B (en este caso, 7), y obtenemos 0 + 7 = 7. Comparamos ese valor con la mínima distancia de B (infinito); el valor más pequeño es el que queda como la distancia mínima de B (en este caso, 7 es menos que infinito):

Bien. Ahora revisaremos al vecino A. Sumamos 0 (la distancia mínima de C, nuestro nodo actual) con 1 (el peso de la arista que conecta nuestro nodo actual con A) para obtener 1. Comparamos ese 1 con la mínima distancia de A (infinito) y dejamos el menor valor:

OK. Repetimos el procedimiento para D:

Genial. Hemos revisado todos los vecinos de C. Por ello, lo marcamos como visitado. Representemos a los nodos visitados con una marca de verificación verde:

Ahora debemos seleccionar un nuevo nodo actual. Ese nodo debe ser el nodo no visitado con la menor distancia mínima, es decir, el nodo con el menor número y sin marca de verificación verde. En este caso, ese nodo es A. Vamos a marcarlo con el punto rojo:

Ahora, repetimos el algoritmo. Revisamos los vecinos de nuestro nodo actual, ignorando los visitados. Esto significa que solo revisaremos B.

Para B, sumamos 1 (la distancia mínima de A, nuestro nodo actual) con 3 (el peso de la arista conectando a A con B) para obtener 4. Comparamos ese 4 con la distancia mínima de B (7) y dejamos el menor valor: 4.

Después, marcamos A como visitado y elegimos un nuevo nodo: D, que es el nodo no visitado con la menor distancia mínima.

Repetimos el algoritmo de nuevo. Esta vez, revisamos B y E.

Para B, obtenemos 2 + 5 = 7. Comparamos ese valor con la distancia mínima de B (4) y dejamos el menor valor (4). Para E, obtenemos 2 + 7 = 9, lo comparamos con la distancia mínima de E (infinito) y dejamos el valor menor (9).

Marcamos D como visitado y establecemos nuestro nodo actual en B.

Casi terminamos. Sólo debemos verificar E. 4 + 1 = 5, que es menos que la distancia mínima de E (9), así que dejamos el 5. Marcamos B como visitado y establecemos E como el nodo actual.

E no tiene vecinos no visitados, así que no verificamos nada. Lo marcamos como visitado.

Como no hay nodos no visitados, ¡terminamos! La distancia mínima de cada nodo ahora representa la mínima distancia entre ese nodo y el nodo C (el nodo que elegimos como nodo inicial).

Aquí está una descripción del algoritmo:

1. Marca el nodo inicial que elegiste con una distancia actual de 0 y el resto con infinito.
2. Establece el nodo no visitado con la menor distancia actual como el nodo actual A.
3. Para cada vecino V de tu nodo actual A: suma la distancia actual de A con el peso de la arista que conecta a A con V. Si el resultado es menor que la distancia actual de V, establécelo como la nueva distancia actual de V.
4. Marca el nodo actual A como visitado.