Apuntes algoritmo Dijkstra

Prévia do material em texto

Apuntes “Algoritmo Dijkstra” 
Para ilustrar como opera el Algoritmo Dijkstra detalladamente lo haremos con un problema presentado en el libro “Investigación de Operaciones, Aplicaciones y algoritmos” del autor Wayne Winston con la siguiente red.
2
3
4
2
4
2
6
1
3
2
3
3
5
Lo primero que debemos verificar en la red es que la distancia o costos de todos los arcos sean no negativos. Dijkstra opera de manera efectiva con cualquier tipo de red, es decir que si la red tiene solamente arcos dirigidos o arcos no dirigidos o una combinación de ambos tipos de arcos no hay ningún inconveniente para la aplicación de este algoritmo.
Es importante mientras se van realizando las iteraciones mantener siempre a la vista la red del problema, normalmente en estos problemas siempre nos indican desde que nodo de origen a que nodo de destino debemos determinar la ruta más corta. En la mayoría de los libros de IO normalmente este nodo de origen es aquel situado en la red a la izquierda de primero y el nodo de destino ubicado a la derecha de último. Sin embargo, Dijkstra permite hallar la ruta más corta desde un nodo de origen a los demás nodos por lo que el nodo de origen puede estar ubicado en cualquier lugar de la red.
Ahora bien, en este problema nos indican que el nodo 1 es el origen, por lo que siempre este se debe hacer permanente y lo indicaremos con la variable “P” y le asignamos siempre una distancia de cero el cual lo indicaremos con una variable “Vi” para luego generar una tabla como la siguiente seria nuestra iteración de inicio.
Iteración “0”
	*V1
	V2
	V3
	V4
	V5
	V6
	0
	∞
	∞
	∞
	∞
	∞
En la tabla anterior el “*” en la variable V1 nos indica que el nodo 1 es permanente con distancia cero, los valores en las demás variables son muy grandes o infinitos al principio, pero a medida que se van realizando las iteraciones estos se van actualizando.
Entonces, ya sabemos que el nodo 1 es permanente y se debe ver desde este nodo a cual otro es posible trasladarse por un solo arco, pero si se permite el traslado solo uno de los dos nodos de cada arco debe ser permanentemente y en caso de que ambos nodos sean permanentes no se debe considerar este arco para los cálculos, en la red del problema vemos que desde el nodo 1 es posible trasladarse por un solo arco al nodo 2 y 3. 
P=1, V1=0
V2= (V2, V1 + C12)
V2= (∞, 4), se debe elegir el más pequeño de los dos.
V3= (V3, V1 + C13)
V3= (∞, 3), se debe elegir el más pequeño de los dos.
Una vez realizado los cálculos anteriores, estos reemplazan a los valores de V2 y V3 que están en la tabla anterior para luego ver cuál de todos los nodos tiene la distancia más pequeña para hacerlo permanente, este proceso continua hasta que todos los nodos sean permanentes. 
Iteración “1”
	*V1
	V2
	*V3
	V4
	V5
	V6
	0
	4
	3
	∞
	∞
	∞
P=3, V3=3
V5= (V5, V3 + C35)
V5= (∞, 6)
Iteración “2”
	*V1
	*V2
	*V3
	V4
	V5
	V6
	0
	4
	3
	∞
	6
	∞
P=2, V2=4
V4= (V4, V2 + C24)
V4= (∞, 7)
V5= (V5, V2 + C25)
V5= (6, 6)
Iteración “3”
	*V1
	*V2
	*V3
	V4
	*V5
	V6
	0
	4
	3
	7
	6
	∞
P=5, V5=6
V6= (V6, V5 + C56)
V6= (∞, 8)
Iteración “4”
	*V1
	*V2
	*V3
	*V4
	*V5
	V6
	0
	4
	3
	7
	6
	8
P=4, V4=7
V6= (V6, V4 + C46)
V6= (8, 9)
Iteración “5”
	*V1
	*V2
	*V3
	*V4
	*V5
	*V6
	0
	4
	3
	7
	6
	8
Aquí, ya hemos encontrando la distancia más corta desde el nodo 1 al nodo 2, 3, 4, 5 y 6. Entonces en el problema del libro nos piden hallar la ruta corta desde el nodo 1 al nodo 6, ya sabemos que la ruta completa desde estos nodos tiene una distancia mínima de 8, así que señalamos cual o cuales rutas tienen esta longitud, no es necesario señalar todas las rutas en realidad basta solamente indicar una ruta con longitud de 8.
 
2
3
4
2
4
2
6
1
3
2
3
3
5
La ruta 1-2-5-6 tiene longitud de 8.
La ruta 1-3-5-6 tiene longitud de 8.
Nota: repito otra vez que basta solamente con indicar una sola ruta.
Ahora resolveremos un problema presentado en el libro “Métodos Cuantitativos para los negocios” de Render&Starir&Hanna con la siguiente red. 
200
4
2
100
100
100
6
150
1
50
100
40
200
5
3
En igual forma que el problema anterior el nodo 1 es el origen por lo que generamos nuestra iteración de inicio a continuación.
Iteración “0”
	*V1
	V2
	V3
	V4
	V5
	V6
	0
	∞
	∞
	∞
	∞
	∞
P=1, V1=0
V2= (V2, V1 + C12)
V2= (∞, 100)
V3= (V3, V1 + C13)
V3= (∞, 200)
Iteración “1”
	*V1
	*V2
	V3
	V4
	V5
	V6
	0
	100
	200
	∞
	∞
	∞
P=2, V2=100
Nota: viendo la red vemos que podemos ir desde el nodo 2 al nodo 1, 3, 4 y 5. Sin embargo el arco (2,1) está formado por dos nodos permanentes así que el nodo 1 no se debe considerar para los cálculos.
V3= (V3, V2 + C23)
V3= (200, 150)
V4= (V4, V2 + C24)
V4= (∞, 300)
V5= (V5, V2 + C25)
V5= (∞, 200)
Iteración “2”
	*V1
	*V2
	*V3
	V4
	V5
	V6
	0
	100
	150
	300
	200
	∞
P=3, V3=150
V5= (V5, V3 + C35)
V5= (200, 190)
Iteración “3”
	*V1
	*V2
	*V3
	V4
	*V5
	V6
	0
	100
	150
	300
	190
	∞
P=5, V5=190
V4= (V4, V5 + C54)
V4= (300, 340)
V6= (V6, V5 + C56)
V6= (∞, 290)
Iteración “4”
	*V1
	*V2
	*V3
	V4
	*V5
	*V6
	0
	100
	150
	300
	190
	290
P=6, V6=290
V4= (V4, V6 + C64)
V4= (300, 390)
Iteración “5”
	*V1
	*V2
	*V3
	*V4
	*V5
	*V6
	0
	100
	150
	300
	190
	290
Aquí finaliza el algoritmo ya que todos los nodos permanentes, también tenemos la distancia más corta desde el nodo 1 al nodo 2, 3, 4, 5 y 6. Como el nodo de destino es el nodo 6 debes ubicar en la red aquella ruta con valor de 290.
200
4
2
100
100
100
6
150
1
50
100
40
200
5
3
La ruta 1-2-3-5-6 tiene longitud de 290, por lo que esta es nuestra ruta óptima.