Flotilla de vehculos Felipe Villanueva 2007-6819 PUCMM Recinto Santo Toms de Aquino fvillanueva.d@gmail.com

ABSTRACTO En este documento se presentar la solucin dada al problema de encontrar la ruta ms corta para recorrer la mayor cantidad de puntos posibles. De este modo, se puede planificar la ruta para que un almacn dado pueda distribuir sus productos de manera eficiente, tanto en trminos econmicos como de tiempo. Trminos generales Algoritmos, Medicin, Eficiencia, Rendimiento, Administracin. 1. INTRODUCCION El problema que aborda el cdigo en cuestin trata sobre encontrar la ruta que abarque la mayor cantidad de puntos posibles. El problema se abord a travs de la teora de grafos y el algortimo de Dijkstra. Se desarroll en el lenguaje C a travs del compilador DevC++ versin 4.9.9.2. 2. Grafos Un grafo es un conjunto de objetos llamados vrtices o nodos unidos por aristas para representar puntos en un mapa y medir la distancia relativa entre un punto y otro.

Figura 1. Ejemplo de grafo Desde un punto de vista prctico, los grafos permiten estudiar las interrelaciones entre unidades que interactan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vrtices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalmbricas).

Sin embargo, en este caso he utilizado grafos para representar las distancias de un punto a otro, logrando la posibilidad de analizar punto a punto la ruta a recorrer.

3. Ruta ms corta Como mencion anteriormente, para encontrar una buena ruta estimada. El cdigo que desarroll tiene dos formas de recibir los datos: una es leyendo un archive de texto con una matriz en un format especfico y la otra es pidiendo manualmente la cantidad de nodos y las distancias al usuario, en caso de no encontrar el archivo de texto. 3.1 Lectura de grafo desde archivo La forma en la que se deben escribir los datos en el archive de texto es como se muestra en la figura 2:

Figura 2. Modo de entrada de datos La forma de escribir los datos en el archivo de texto, tal como se muestra en la figura es escribir la misma cantidad de filas y de columnas (hasta 10, los no usados deben llevar un cero). Como el programa nombra los nodos del cero al nueve y utiliza la matriz como una tabla de distancias (las filas y las columnas son los mismos nodos del 0 al 9) debe de escribirse un cero en las interseccion (0,0), (1,1), etc para que el programa no devuelva error. En caso de leer el archivo correctamente se procede inmediatamente a encontrar la ruta estimada y muestra una pantalla como la siguiente:

Figura 3. Ruta estimada desde grafo ledo de archivo Como podemos observar, la ruta se presenta como la secuencia de nodos a seguir. 3.2 Lectura de datos desde el usuario En caso de no encontrarse el archive Grafo.txt, se procede a indicarle al usuario dicha situacin y se le pregunta si desea digitar manualmente un grafo y la cantidad de nodos, en caso de decir que si.

Figura 4. Ingreso manual de grafos 3.3 Algoritmo del programa El programa se comporta de acuerdo al siguiente algoritmo: InicioAbrir Grafo.txt de la carpeta del programaArchivo abierto con xitoSiNoCrear matrizLeer Grafo.txtencontrarRuta() Solicitar cantidad de nodos y las distanciasCrear matriz de distanciasLlenar matriz de distanciasImprimir grafoImprimir grafoMostrar rutaSalir Figura 5. Algoritmo general del programa En donde la parte principal es la funcin encontrarRuta cuyo cdigo presento en la siguiente seccin. Dicho cdigo tiene un

tiempo de ejecucin que tiende a N^2 debido a la implementacin de la matriz bidimensional.

3.4 Cdigo para encontrar la ruta

int encontrarRuta() { int menor=0, cambio=0, temp=0, k=1; menor=65535;

GLeidos[0]=1; ruta[0]=0; i=0;

while(1