Prueba

PEREZ SANCHEZ JOSE LUIS

MATRICULA: 210369343

PROYECTO: RUTA MAS CORTA

PROFESOR: DR. ALEXANDER SCHAUM

25 – 07 - 2011
INDICE

INTRODUCCION ………………………………………………………………………….3
GRAFO DE CIUDADES …………………………………………………………………4
ANALISIS DEL PROBLEMA ………………………………………………………….5
DEFINICION DE VARIABLES IMPORTANTES ………………………………..8
DISEÑO DE DIAGRAMAS DE BLOQUES ……………………………………..9
ALGORITMOSUTILIZADOS ………………………………………………………10
CODIFICACION EN C (funcion main)………………………………………….12
PROTOTIPOS DE FUNCIONES (FUNCIONES.h) …………………………..15
SALIDAS DEL PROGRAMA ……………………………………………………… 16
BIBLIOGRAFIA ………………………………………………………………………..18

INTRODUCCION
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vérticeorigen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en 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 quecomponen el grafo, el algoritmo se detiene. Las aristas deben tener un peso no negativo.
Una posible aplicación de este algoritmo se presenta cuando se desea encontrar la ruta más corta entre dos ciudades; cada vértice representa una ciudad y las aristas representan los kilómetros entre las ciudades.
En particular se han elegido ciudades de los estados de Chihuahua, Durango, Zacatecas yCoahuila para poder encontrar la ruta más corta entre cualquiera de ellas.

GRAFO DE CIUDADES

JUAREZ
(CHIHUAHUA)
MONCLOVA
(COAHUILA)
ZACATECAS
(ZACATECAS)
SALTILLO
(COAHUILA)
DURANGO
(DURANGO)
CHIHUAHUA
(CHIHUAHUA)
FRESNILLO
(ZACATECAS)
MAPIMI
(DURANGO)
1,088.400 km

364.000 km
366.000 km
191.000 km
340.000 km
796.400 km
377.360 km
437.030 km
58.900 km
301.540 km
291.580km
688.480 km
351.500 km
444.900km

ANALISIS DEL PROBLEMA
Como entrada son los vértices inicial y final de la ruta, aplicamos el algoritmo de Dijkstra y como resultado se imprime la ruta más corta entres las ciudades inicial y final.
Como ejemplo, vamos a suponer que deseamos conocer la ruta más corta entre Chihuahua(Chihuahua) y Saltillo(Coahuila).
Etiquetamos los nodos:
0 =CHIHUAHUA(CHIHUAHUA)
1 = CD. JUAREZ (CHIHUAHUA)
2 = MONCLOVA (COAHUILA)
3 = SALTILLO (COAHUILA)
4 = ZACATECAS (ZACATECAS)
5 = DURANGO (DURANGO)
6 = MAPIMI (DURANGO)
7 = FRESNILLO (ZACATECAS)
Vamos a considerar la siguiente nomenclatura (k,m) donde k = peso y m = Vértice de donde viene la suma de pesos.
En nuestro caso comenzamos con (0,0), nos fijamos en los vértices adyacentes del nodo 0 (Juárez,Mapimí y Durango), elegimos el nodo con menor peso = Juárez, lo marcamos y hacemos la suma de pesos del nodo elegido con el origen, en nuestro caso 0+351.500=351.500. Ahora nos fijamos en los nodos adyacente a Juárez y en sus pesos (Monclova y Mapimí), Mapimí ya lo habíamos considerado previamente (Chuhuahua - Mapimí), en caso de que hubiese sido menor la ruta Juárez – Mapimí, sustituye aChihuahua – Mapimí, ésta consideración es muy importante ya que es muy frecuente que se olviden, las sustituciones de rutas previamente consideradas por una menor.
En nuestro caso elegimos la ruta más corta entre:
Juárez – Monclova = 1088.400
Chihuahua – Mapimí = 444.900
Chihuahua – Durango = 688.480
Elegimos Chihuahua – Mapimí Marcamos el nodo Mapimí y sumamos los pesos 0+444.900=444.900
Ahoraobservamos los nodos adyacentes a Mapimí(Durango, Zacatecas, Fresnillo, Monclova) no marcados y nos fijamos en la ruta más corta, considerando también las rutas pendientes que tenemos y sustituyéndolas por una ruta menor en caso de que exista:
Chihuahua – Durango = 688.480 es sustituida por Mapimí – Durango = 291.580
Mapimí – Zacatecas = 437.030
Mapimí – Fresnillo = 377.360
Juárez – Monclova...