pedagogia

Páginas: 5 (1042 palabras) Publicado: 10 de junio de 2013
RUTA MAS CORTA ENTRE DOS NODOS DE CUALQUIER GRAFO (ALGORITMO DE DIJKSTRA)

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, 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 alos 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.

EJEMPLO:
Tengamos el siguiente grafo, cuyos ID están en color negro encima decada 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.
// *****************************PASO 1*******************************

Inicializamos los valores de nuestros arreglos


Donde:
Vértices: ID de los vértices.
Distancia[ u ]: Distancia mascorta 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:
// *****************************PASO 2*******************************

Y lafunción de inicialización será simplemente lo siguiente
// *****************************PASO 3*******************************

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.
//*****************************PASO 4*******************************

Extraemos el tope de la cola de prioridad
// *****************************PASO 5*******************************

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

En este caso al ser el tope elinicial no está visitado por lo tanto marcamos como visitado.
// *****************************PASO 7*******************************

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.
// *****************************PASO 8*******************************

Evaluamos primero para vértice 2

Vemos que ladistancia 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 siguienteparte:
// *****************************PASO 9*******************************

Donde la función de relajación seria
// *****************************PASO 10*******************************

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 serían vértices 2, 3 y 5.
Empecemos por el vértice 2:...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Pedagogia
  • Pedagogia
  • Pedagogia
  • Pedagogía
  • Pedagogia
  • Pedagogia
  • Pedagogia
  • Pedagogia

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS