algoritmo camino mas corto

Introducción
1
El problema de colorear un mapa plano con la menor cantidad posible de
colores de manera que no hubiesen dos regiones limítrofes con el mismo color ha
sido un problema de interés desde hace mucho tiempo. Pero el teorema de los
cuatro colores fue planteado por Francis Guthrie
a principios de la década de
1850.
2
Muchos matemáticos intentaron demostrar el teorema deGuthrie (que hasta ese
entonces no era mas que una conjetura) y el 13 de Junio de 1878 Arthur Cayley
envió una carta a la Sociedad Matemática de Londres preguntando si la conjetura
de los cuatro colores ya había sido resuelta.
El 17 de Julio de 1879, Alfred Bray Kempe
anunció que tenía una demostración
de la Conjetura de los Cuatro Colores. El Teorema y su demostración fueron
publicados en elPeriódico Americano de Matemáticas en 1879.
3
En 1890 un conferencista de Durham, Inglaterra, llamado Percy John Heawood
publicó el ensayo El Teorema del Coloreo de Mapas donde mostraba que la prueba
de Kempe estaba era errónea.
Fue en 1976 cuando, finalmente, se resolvió la Conjetura de los Cuatro Colores.
La prueba fue obtenida por Appel y Haken, quienes trabajaron sobre los métodos
quehabía utilizado Kempe y otros métodos creados en los últimos años. Appel y
Haken utilizaron 1200 horas de computadora para trabajar en la prueba final.
El Teorema de los Cuatro Colores fue le primer gran teorema en ser demostrado
usando una computadora, teniendo una demostración que pudo ser verificada
directamente por los matemáticos. Los detalles de la demostración aparecieron en
dospublicaciones en 1977. Trabajos recientes han llevado a mejoras en el
algoritmo.
En el presente trabajo se muestra el desarrollo de tres algoritmos para el coloreo
de mapas y la optimización del último de ellos. Los algoritmos fueron programados
en PHP y una versión interactiva del último algoritmo optimizado fue realizada en
Macromedia Flash
1
4
.


Algoritmo del camino mas corto
Problema delCamino Mínimo
 
Consiste en encontrar la ruta más corta entre dos puntos. Este problema es válido para encontrar la distancia más corta, o hallar el menor tiempo en llegar desde un punto a otro. Viendo esto a nivel de un grafo, el problema es encontrar el mejor recorrido entre dos nodos, donde los pesos de las aristas pueden representar la distancia o el tiempo.
Existen diferentes algoritmosque resuelven este problema, tales como el de Floyd, Dijkstra o Bellman-Ford, que trabajan en base a grafos. En una breve descripción, el algoritmo de Floyd encuentra el camino entre todos los pares de vértices en una única ejecución, Dijkstra determina el camino más corto, en un grafo dirigido, entre un nodo determinado con el resto de los nodos del grafo, el cual la distancia entre cada nodo esno negativa, y Bellman-Ford cumple la misma tarea pero incluyendo aristas con pesos negativos en el grafo.

Algoritmo
Se usará el algoritmo de Dijkstra, ya que el tiempo de ejecución es menor al de Floyd(O(n3), y Dijkstra O(|V|2)), por el hecho de usar solo un nodo de origen. El algoritmo de Bellman-Ford es utilizado solamente para casos en donde existan grafos con los pesos de aristasnegativos.
 
La solución se divide en 3 pasos:
1. Se selecciona un nodo no visitado con la menor distancia acumulada.
2. La distancia acumulada que se tiene hasta el momento se suma a la distancia de las aristas que van dirigidos a los nodos que se pueden acceder.  Si en esos nodos a los que se puede acceder existe distancia acumulada, se compara con la nueva, y se conserva la menor.
3. El nodoactual se marca como visitado y se vuelve al primer paso.
Con esta información se podrá conocer la distancia más corta entre dos pueblos determinados. Para el problema del camino mínimo, se usará los nodos como pueblos, y los pesos de las aristas como la distancia entre dos pueblos vecinos, expresada en Km.
Ejemplo:
En la figura 1 se puede apreciar un grafo, donde los nodos A, B, C, D, E y F...