Proyecto 5

“Algoritmo de Dijkstra”

Definición

El algoritmo de Dijkstra fue descubierto por el matemático holandés Edsger Dijkstra en 1959, es también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.

La idea de este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.

Su complejidad computacional es perteneciente a P ya que se puede resolver en tiempo polinomial, siempre y cuando las distancias o los pesos no sean negativos. Y como lo hemos visto en clase anteriormente cuando su complejidad es P este puede ser resuelto por una maquina turing no determinista en tiempo polinomial.

Algoritmo

Pues principalmente construiremos un grafo con N nodos, y tomaremos como x el nodo inicial, también un vector D de tamaño N ósea que va a ir guardando hasta el final del algoritmo las distancia desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.

2. Sea a = x (tomamos a como nodo actual).

3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos v_i.

4. Si la distancia desde x hasta v_i guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta v_i; esta se sustituye con la segunda nombrada, esto es:
si (D_i > D_a + d(a, v_i)) entonces D_i = D_a + d(a, v_i)

5. Marcamos como completo el nodo a.

6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

Complejidad Computacional

El Algoritmo de Dijkstra realiza O(n²) en donde n es el numero de operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

La Explicacion del mismo:

Podemos estimar la complejidad computacional del algoritmo de Dijkstra (en términos de sumas y comparaciones). El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se añade un vértice al conjunto distinguido. Para estimar el número total de operaciones basta estimar el número de operaciones que se llevan a cabo en cada iteración. Podemos identificar el vértice con la menor etiqueta entre los que no están en S_k realizando n-1 comparaciones o menos. Después hacemos una suma y una comparación para actualizar la etiqueta de cada uno de los vértices que no están en S_k. Por tanto, en cada iteración se realizan a lo sumo 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas por actualizar en cada iteración. Como no se realizan más de n-1 iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones.

Pseudocódigo

Tratare de explicar en un pseudocódigo sencillo la funcionalidad del algoritmo.

· G = (V,E) donde V es el conjunto de vértices y E el de arcos.

· S es el conjunto de vértices cuyos caminos más cortos al origen han sido ya determinados.

· V-S es el resto de vértices.

· d: ARRAY de estimaciones de caminos más cortos a dichos vértices.

· pr: ARRAY de predecesores para cada vértice.

<d y pr>>

<S = Æ>> // aún no hemos estudiado ningún vértice

While {V-S} // mientras queden nodos sin determinar su camino mínimo al origen

<V-S Æ y analizar de acuerdo a la menor distancia al origen>>

<u, el vértice más cercano en V-S, a S>> // S = S + {u}

< vértices todavía en V-S adyacentes a u>>>

Aqui un Video De Como Funciona El Algoritmo De Dijkstra

Ejemplo "Paso a Paso"

Supongamos el siguiente grafo:

Cogemos por ejemplo el nodo N1. La distancia acumulada será cero, porque es el primero. Comenzamos a aplicar los tres pasos que forman nuestro heurístico.

1) El nodo N1 es la menor distancia acumulada puesto que es el nodo inicial.

2) Tenemos a N5 una distancia de 1 y a N2 una distancia de 5. A N4 y a N3 no podemos acceder puesto que no tenemos aristas que nos comuniquen con ellos. Puesto que no hay ninguna distancia acumulada la menor distancia será 1 y 5.

3) Ponemos N1 como nodo visitado.

1) Elegimos N5 puesto que es el nodo con menor distancia acumulada (N2 tiene 5).

2) Tendremos a N4 una distancia de 11 (1 acumulado + 10 de la arista). A N3 una distancia de 4. A N2 no podemos acceder y N1 es nodo visitado.

3) Ponemos N5 como nodo visitado.

1) Elegimos ahora N3 que es el nodo con menos valor acumulado. N4 tiene 11 y N2 tiene 5.

2) A N4 tendremos una distancia de 10, que mejora los 11 que tenemos acumulados, luego nos quedamos con ese valor en lugar del 10. A N2 tenemos una distancia de 6 que no mejora el 5, luego seguimos con el 5.

3) Marcamos N3 como visitado.

1) Elegimos N2 puesto que es el nodo no visitado con menor distancia acumulada.

2) A N4 tendremos una distancia de 6 que mejora los 10 actuales, luego nos quedaremos con el 6.

3) Marcamos N2 como nodo visitado.

Sólo nos queda el último nodo que no puede acceder a ningún otro luego lo marcamos también como visitado.

Ahora tendremos acumuladas en cada nodo la distancia más corta desde N1.

Implementación del Algoritmo

Programa en dev-c que me permite saber cual es el camino mas corto dado n vértices y sus respectivos pesos.

Aplicación del Algoritmo

Las aplicaciones del algoritmo de Dijkstra son muy diversas y de gran importancia en distintas áreas del conocimiento un ejemplo podria ser:

<<<<Encaminamiento de paquetes por los routers>>>>

Consideremos una red telefónica. En un momento dado, un mensaje puede tardar una cierta cantidad de tiempo en atravesar cada línea (debido a efectos de congestión, retrasos en las conexiones etc.). En este caso tenemos una red con costes en los arcos y dos nodos especiales: el nodo de comienzo y el de finalización, el objetivo aquí es encontrarun camino entre estos dos nodos cuyo coste total sea el minimo.

Mi Presentacion

Algoritmo de dijkstra final

View more presentations from salomon.

Link de Mi Presentacion:

-http://www.slideshare.net/salomonkarr/algoritmo-de-dijkstra-final

Bibliografia

-http://www.youtube.com/watch?v=6rl0ghgPfK0&feature=related

-http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

-http://neo.lcc.uma.es/evirtual/cdd/applets/distancia%20corta/Example2.html

-http://www.it.uc3m.es/~pablo/asignaturas/rysc1/alumnos/04-EncEjerciciosSolucion.pdf

-http://156.35.31.178/wiki/index.php/TP:Algoritmo_de_Dijkstra_-_Algoritmos_voraces