Algoritmo de Dijkstra
Nicolas Ignacio Pino Cea
n.pino02@[Link]
Universidad de la Frontera
RESUMEN: En este informe se mostraran ALGORITMO GREEDY
Los resultados de una investigacin sobre
El Algoritmo de Dijkstra. Se dejara en claro Tambin Conocido como algoritmo voraz, la lgica de este
En que consiste, ejemplos y aplicaciones Tipo de cdigo es que en cada paso se van evaluando las
De este mtodo. Soluciones obtenidas si son o no optimas para el problema.
PALABRAS CLAVES: Algoritmo, Aplicacin PRINCIPIO OPTIMALIDAD DE BELLMAN
Caminos Mnimos, Optimizacin.
INTRODUCCIN Principio que se aplica en programacin dinmica, que
Indica que en una serie de procesos ptimos, cualquier
Subprocesos tambin es ptimo.
Cuando por algn motivo nos retrasamos y
necesitamos llegar a un destino, y lo mas rpido posible,
tratamos de recorrer el trayecto ms corto para llegar a tiempo
a tal lugar. Con estas definiciones, ya podemos empezar a hablar de
Nuestro tema principal.
En la asignatura de matemticas Discretas y,
especficamente en el tema de grafos, se planteo
estudiar un mtodo que tiene mucha relacin con la
situacin descrita inicialmente, este mtodo es el ALGORITMO DE DIJKSTRA
algoritmo de Dijkstra. El creador de este algoritmo es
Edsger Wybe Dijkstra, un fsico terico Holands, quien
destaco en el rea de la computacin. Dijkstra plantea y
Sea G un grafo dirigido, V conjunto de vrtices, vrtice
resuelve el problema de cmo llegar de una ciudad a otra,
inicial y el valor de cada arista.
teniendo distintos caminos, de la forma mas corta posible. De
esta manera crea el algoritmo de los caminos mnimos.
Dijkstra, por cada iteracin, iniciando desde , va a tomar
la arista que menor valor genere. As lo har hasta llegar al
En trminos mas tcnicos el algoritmo trata de ir de
punto objetivo. Por cada paso se ira guardando en un vector
vrtice a vrtice, donde tiene variadas alternativas, analizando
D los puntos por los cuales se dirige el algoritmo y guarda
y evaluando por cual arista seguir, como resultado debe
en otra celda con el valor mnimo obtenido. Encontrando el
obtener el camino mnimo. Esta tcnica tiene diferentes
camino mas ptimo.
aplicaciones, en el campo de Internet, todo lo relacionado a
redes, planificaciones de ruta, por nombrar algunos.
Comentarios
- El valor de las aristas no puede ser negativo.
- Los valores de las arista se pueden guardar en una
matriz de dimensin V x V. En programacin es
muy til esta accin.
DESARROLLO
Para entender de la manera mas clara posible - En la literatura, al valor de las aristas se le puede
El Algoritmo de Dijkstra vamos a definir algunos principios llamar pesos.
y/o conceptos:
Pseudocdigo
Como cualquier algoritmo, se puede implementar en distintos En este nuevo vrtice debemos repetir el paso anterior. El
lenguajes, ya sea JAVA, C++ , PYTHON. La programacin vector resultante es ABC con valor minimo 3.(Fig.2).
bsica es la siguiente.
Inicio M, , ,K y V
Mientras V - D =!
Escoger , en V - D con MINIMO
Hacer D = D+ { }
Para en V - D
Si > + Figura 2
Hacer = +
Fin Tenemos 2 caminos nuevamente, se escoge el de menos valor.
Fin La ruta queda determinada por el vector ABCD, con un valor
Fin de 10. (Fig.3).
Donde:
M = Matriz con valores de cada arista, dimensin N x N.
V = Conjunto de vrtices.
K = Conjunto del valor mnimo.
D = Elementos de conjunto de vrtices mnimos.
= Vrtice Inicial.
Figura 3
Ejemplo
A continuacin, se veremos un ejemplo, bastante
Sencillo pero claro, de cmo funciona el algoritmo de Dijkstra Continuando con el algoritmo llegamos al resultado
Final, donde el vector resultante es ABCDF y con un valor
Primero elegimos la arista con menor peso, en este caso mnimo de 17. (Fig.4). Cabe mencionar que ese vector y valor
AB y con un valor de 2. (Fig.1). mnimo pueden tener distintas interpretaciones, segn el
contexto.
Tenemos 2 caminos nuevamente, se escoge el de
menos valor. La ruta queda determinada por el vector
ABCD, con un valor de 9. (Fig.4).
Figura 1 Figura 4
Aplicaciones Mario Aldea Rivas, Programacin II, [Online], Tema 5.
Algoritmos voraces, heursticos y aproximados, 2011
Debido a su simpleza y efectividad, este algoritmo tiene Disponible en:
aplicaciones en variados campos
[Link]
es/05_voraces_3en1.pdf
Planificaciones de ruta
El origen del algoritmo trataba de esto, con el tiempo se ha ido Jose Antonio Abia Vian, Algoritmo de Dijkstra, [Online], XII
mejorando y se ejecutan planificaciones de transporte, para laboratorio: Teora de grafos, 1.3 Camino de peso mnimo,
empresas de camiones, para empresas viales y todo el rubro que Disponible en:
solicite un estudio de distancias.
[Link]
Problema de trafico Bangkok 10/LabM/Grafos-2010_4.pdf
Este fue un problema real, en la zona metropolitana de Bangkok se
utilizo el algoritmo de Dijkstra para solucionar el el problema de Alexander Xavier Falcao, Images Foresting Transform,
trfico y transporte. [Online], Brasil: University of Campinas, Disponible en:
Redes Inalmbricas [Link]
ectureNotes/[Link]
En el rea de redes, asociado a internet, se aplica el algoritmo para
establecer rutas de con el fin de mejorar la conexin y traspaso de
informacin.
IFT
Dijkstra se utiliza en una herramienta IFT (Images Foresting
transform) , que es un sistema de procesamiento de imgenes.
BIBLIOGRAFA
FCEN, Algoritmos para determinar caminos mnimos en
grafos,[Online], Argentina: Universidad de Buenos Aires,2012
Disponible en:
http :/ / [Link]. ar/ materias /aed3/2012-01
/Documents/ algo3_cammi nv 3_ho.pdf
Hamilton Richard, Edsger Wybe Dijkstra, [Online], A.M. Turing
Awards. Disponible en:
[Link]
World Academy of Science, Engineering and Technology
International Journal of Social, Behavioral, Educational, Economic
and Management Engineering, Public Transport Planning System
by Dijkstra Algorithm: Case Study Bangkok Metropolitan Area,
[Online], Vol:8, No:1, 2014, Disponible en:
[Link]
planning-system-by-dijkstra-algorithm-case-study-bangkok-
metropolitan-area
