Mes XI de Año MMXVII. Universidad Tecnológica de Pereira.
Algoritmo de Dijkstra y algoritmo de Prim
Dijkstra’s algorithm and Prim’s algorithm.
Autores: Cristian Andres Arce Pineda
Miguel Angel Henao
Risaralda, Universidad tecnológica de Pereira, Pereira, Colombia
Correo-e: [Link]@[Link]
Resumen— El algoritmo de Dijkstra y de Prim son algoritmos
de optimización muy utilizados actualmente, existen diferentes II. CONTENIDO
formas de implementarlos, sin embargo todas son sencillas y
fáciles de comprender. Su principal objetivo es acortar caminos, 1. Algoritmo de Dijkstra
ya sea para ahorrar tiempo, dinero o recursos.
1.1. Definición de Dijkstra
1.2. Aplicaciones de Dijkstra
Palabras clave— Algoritmo, árbol de expansión mínimo, arista,
grafo conexo, grafo dirigido, grafo etiquetado, trayectoria,
1.3. Ejemplo de Dijkstra
vértice. 1.4. Código de Dijkstra C++
2. Algoritmo de Prim
Abstract—Dijkstra´s and Prim´s algorithms are optimization 2.1. Definición de Prim
algorithms widely used today, there´re different forms to 2.2. Aplicaciones de Prim
implement them, nevertheless everyone are simple and easy to 2.3. Ejemplo de Prim
understand. Their main objective is to reduce roads to save time, 2.4. Código de Prim C++
money or resources. 3. Conclusiones
Recomendaciones
Key Word —Algorithm, minimum spanning tree, edge, weighted Referencias
graph, directed graph, tagged graph, path, vertex.
1. Algoritmo de Dijkstra
I. INTRODUCCIÓN
1.1. Definición de Dijkstra
Como podemos ver, en la vida cotidiana, se presentan
constantemente problemas sobre qué ruta seguir, por cual Dijkstra es un algoritmo cuya finalidad es determinar el
camino se llega más rápido a un determinado lugar y cuál es camino más corto de un punto a otro. Para esto recibe un
la distancia más corta de un punto a otro. Este tipo de grafo, un vértice origen y un vértice destino, lo que hace es
problemas se pueden representar fácilmente en una recorrer el grafo desde el origen hasta el destino, eligiendo el
computadora para ser solucionados con el algoritmo de camino que tenga menor peso, es decir, trabajando por etapas
Dijkstra o con el algoritmo de Prim. toma en cada una la mejor solución sin tener en cuenta
consecuencias futuras.
El holandés Edsger Dijkstra, fue quien describió el algoritmo
de Dijkstra en 1959, también llamado algoritmo de caminos Al terminar el algoritmo es posible conocer la menor
mínimos. trayectoria (los vértices por los que pasó) y cuál fue el costo
del recorrido (peso total de la trayectoria).
El algoritmo de Prim fue diseñando por Vojtech Jarnik en
1930, sin embargo en 1957, Robert C. Prim también lo Para un grafo no dirigido la complejidad del algoritmo es:
describió de una manera independiente a Jarnik, por esta O(n2).
razón al algoritmo de Prim en ocasiones se le llama algoritmo
de Jarnik. Para que el algoritmo funcione correctamente, el grafo debe
ser:
Estos algoritmos son muy utilizados en los campos de la • Conexo
geografía, medicina, telefonía, informática y muchos otros. • Etiquetado
• Dirigido o no dirigido
Más adelante se explicará en qué consiste y cómo funciona
• Los pesos deben ser positivos
cada uno de ellos, utilizando ejemplos puntuales.
[1]. Wikipedia: [Link]
2
Según la página web [1], Teniendo un grafo dirigido de N
nodos, un nodo inicial x, un vector D de tamaño N que • Rodear una montaña por el camino más corto
guardará al final del algoritmo las distancias desde x al resto
de los nodos, los pasos del algoritmo son los siguientes: • Conocer el camino más rápido que sigue la información
a través de las neuronas.
1. Inicializar todas las distancias en D con un valor infinito
relativo, exceptuando la de x que se debe colocar en 0. 1.3. Ejemplo de Dijkstra
2. Sea a = x ( a es el nodo actual).
3. Recorrer todos los nodos adyacentes de a, excepto los En el siguiente ejemplo encontraremos el camino más corto
nodos marcados, (nodos no marcados: vi). para llegar del vértice ‘a’ al vértice ‘z’. Teniendo en cuenta
4. Para el nodo actual, se calcula la distancia tentativa que las aristas rojas son la trayectoria seleccionada y las
desde dicho nodo a sus vecinos con la siguiente fórmula: aristas azules son los posibles caminos. El grafo es el que se
dt(vi) = Da + d(a,vi). Es decir, la distancia tentativa del muestra a continuación:
nodo ‘vi’ es la distancia que actualmente tiene el nodo
en el vector D más la distancia desde dicho el nodo ‘a’
(el actual) al nodo vi. Si la distancia tentativa es menor
que la distancia almacenada en el vector, se actualiza el
vector con esta distancia tentativa. Es decir: Si dt(vi) <
Dvi → Dvi = dt(vi)
5. Se Marca como completo el nodo a.
6. Se toma como próximo nodo actual el de menor valor en
D (puede hacerse almacenando los valores en una cola
Figura 2. Grafo inicial para el ejemplo de Dijkstra
de prioridad) y se vuelve al paso 3 mientras existan
nodos no marcados.
Paso 1: Como se puede observar, existen 3 vértices
Una vez terminado al algoritmo, D estará completamente
adyacentes al grafo: b, c y d. Como ninguno está marcado
lleno.
aún, se elige el camino con menor distancia: a d.
Marcamos el nodo a y el nodo d.
Figura 1. Pasos que sigue el algoritmo Dijkstra partiendo desde 0. Figura 3. Paso 1 del ejemplo de Dijkstra
1.2. Aplicaciones de Dijkstra o Trayectoria: a, d
o Costo: 5
Como dice en [2], Algunas de las aplicaciones de este
algoritmo son: Paso 2: Continuamos considerando los vértices adyacentes a
• Encaminamiento de paquetes por los routers: encontrar d, que son: c y e. (el vértice ‘a’ no se considera porque ya está
el camino más rápido entre dos nodos de una red. marcado). El camino más corto es: d c, por lo tanto se
escoge ese camino y se marca el nodo c.
• Aplicaciones para sistemas de información geográficos:
extracción de características curvilíneas de imágenes
usando técnicas de minimización del camino.
• Reconocimiento de lenguaje hablado: Con un grafo
cuyos vértices son las palabras posibles y las aristas
unan palabras que pueden ir colocadas al lado de las
otras. Si el peso de las aristas corresponde a la
probabilidad de que estén así colocadas, el camino más Figura 4. Paso 2 del ejemplo de Dijkstra
corto en el grafo será la mejor interpretación de la frase.
o Trayectoria: a, d, c
• Tratamiento de imágenes médicas. o Costo: 5 + 4= 9
[2]. [Link]
[3]. [Link]
Scientia et Technica Año XVIII, No xx, Mesxx de Añoxx. Universidad Tecnológica de Pereira. 3
paso 4 ya que se comprobó que era el más corto. Se marcan
Paso 3: Los vértices adyacentes a ‘c’ son: b, f y e (no se los nodos ‘f ’ y ‘e’ y se desmarca el nodo ‘g’.
tienen en cuenta los vértices a y d porque ya están marcados).
Se comparan los pesos de los tres y se elige el camino: c b
por ser tener un peso menor a los demás. Se marca el nodo b.
Figura 8. Paso 6 del ejemplo de Dijkstra
o Trayectoria: a, d, c, b, f, e
Figura 5. Paso 3 del ejemplo de Dijkstra o Costo: 5 + 4+ 2 + 4 + 3= 18
o Trayectoria: a, d, c, b Paso 7: La única arista adyacente a ‘e’ (que no esté marcada)
o Costo: 5 + 4+2= 11 es ‘z’, por lo tanto se elige esa trayectoria y se verifica que
ningún otro camino sea más corto. Se Marca el nodo Z,
Paso 4: El vértice ‘b’ tiene solo dos nodos adyacentes: g y f llegando así al destino.
(porque a y c ya están marcados). El camino más corto es: de
b f. Y se marca el nodo ‘f ’.
Figura 9. Paso 6 del ejemplo de Dijkstra
Figura 6. Paso 4 del ejemplo de Dijkstra o Trayectoria final: a, d, c, b, f, e, z
o Costo: 5 + 4+ 2 + 4 + 3 + 5 = 23
o Trayectoria: a, d, c, b, f 1.4 Codigo Dijkstra C++
o Costo: 5 + 4+ 2 + 4 = 15
#include <stdio.h>
Paso 5: En este paso, es necesario comparar otras opciones #include <vector>
para llegar hasta ‘g’, que puede ser desde ‘f ’ o desde ‘b’, en #include <queue>
este caso el menor costo es: b g ya que 6 < (4 + 8). Por lo using namespace std;
tanto se borra la trayectoria de b f y se reemplaza por la
encontrada anteriormente. Marcando el nodo ‘g’ y struct cmp {
desmarcando el nodo ‘f ’. bool operator() ( const Node &a , const Node &b ) {
return [Link] > [Link];
}
};
vector< Node > ady[ MAX ]; //lista de adyacencia
int distancia[ MAX ];
bool visitado[ MAX ];
priority_queue< Node , vector<Node> , cmp > Q;
int V;
Figura 7. Paso 5 del ejemplo de Dijkstra int previo[ MAX ];
o Trayectoria: a, d, c, b, g void init(){
o Costo: 5 + 4+ 2 + 6 = 17 for( int i = 0 ; i <= V ; ++i ){
distancia[ i ] = INF;
Paso 6: Ahora es necesario comparar si existe un camino visitado[ i ] = false;
menor para llegar a ‘e’, ya que es el nodo de menor costo previo[ i ] = -1 }
desde ‘f ’. de esta manera se vuelve a retomar el camino del }
4
//Paso de relajación ady[ origen ].push_back( Node( destino , peso ) );
ady[ destino ].push_back( Node( origen , peso ) );
void relajacion( int actual , int adyacente , int peso ){ }
if( distancia[ actual ] + peso < distancia[ adyacente ] ){ printf("Ingrese el vertice inicial: ");
distancia[ adyacente ] = distancia[ actual ] + peso; scanf("%d" , &inicial );
previo[ adyacente ] = actual; dijkstra( inicial );
[Link]( Node( adyacente , distancia[ adyacente ] ) ); return 0;
} }
}
2. Algoritmo de Prim
void print( int destino ){
if( previo[ destino ] != -1 ) 2.1. Definición de Prim
print( previo[ destino ] );
printf("%d " , destino } Prim es un algoritmo sencillo y fácil de utilizar perteneciente
a la teoría de grafos, su objetivo es encontrar el árbol de
void dijkstra( int inicial ){ expansión mínima de un determinado grafo, es decir, crea un
init(); nuevo árbol que incluye todos los vértices del grafo original,
[Link]( Node( inicial , 0 ) ); evidenciando solo los caminos más cortos entre ellos (los que
distancia[ inicial ] = 0; tengan menor peso).
int actual , adyacente , peso;
while( ![Link]() ){ La complejidad del algoritmo es: O(n2).
actual = [Link]().first
[Link](); Para que el algoritmo funcione correctamente, el grafo debe
if( visitado[ actual ] ) continue; ser:
visitado[ actual ] = true; • Conexo
for( int i = 0 ; i < ady[ actual ].size() ; ++i ){ • Etiquetado
adyacente = ady[ actual ][ i ].first; //id del vertice
• No dirigido
adyacente
peso = ady[ actual ][ i ].second; / adyacente (
De acuerdo con la página web [3], los pasos del algoritmo
actual , adyacente )
son:
if( !visitado[ adyacente ] ){
1. Iniciar el grafo T con un solo nodo i escogido al azar:
relajacion( actual , adyacente , peso ); } N = {i}, A = 0, T = ({i},0).
} 2. Seleccionar el arco (i, j) cuya longitud es la menor entre
} todos aquellos arcos adyacentes a T. Adicionar este
arco (i,j) a T y j al conjunto de nodos de T.
3. Si T ya es un árbol que contiene todos los nodos del
printf( "Distancias mas cortas iniciando en vertice grafo debe detenerse, en este caso contrario repetir el
%d\n" , inicial ); paso 2.
for( int i = 1 ; i <= V ; ++i ){
printf("Vertice %d , distancia mas corta = %d\n" , i , Nota: se debe de tener en cuenta que las posibles opciones
deben ir de un nodo marcado a un nodo no marcado.
distancia[ i ] );
}
puts("\n**************Impresion de camino mas
corto**************");
printf("Ingrese vertice destino: ");
int destino;
scanf("%d" , &destino );
print( destino );
printf("\n");
}
Figura 10. Secuencia de pasos del algoritmo Prim
int main(){
int E , origen, destino , peso , inicial; 2.2. Aplicaciones de Prim
scanf("%d %d" , &V , &E );
while( E-- ){ Este algoritmo se utiliza para ahorrar recursos, su aplicación
scanf("%d %d %d" , &origen , &destino , &peso ); más común es conocer la mejor forma de conectar cables de
redes, servidores y postes de luz.
[2]. [Link]
[3]. [Link]
Scientia et Technica Año XVIII, No xx, Mesxx de Añoxx. Universidad Tecnológica de Pereira. 5
Paso 3: Ahora los posibles caminos son las aristas adyacentes
2.3. Ejemplo de Prim a D, A y F. La más corta es: A B, entonces se marca el
vértice B. El peso es = 18.
En el siguiente ejemplo se mostrará paso a paso, cómo
funciona el algoritmo de prim para extraer el árbol de
expansión mínimo. Teniendo en cuenta que el color azul claro
representa el nodo con menor peso, el azul oscuro son los
posibles caminos y el color verde, la trayectoria seleccionada.
El grafo inicial es el que muestra a continuación y se
empezará desde el vértice ‘D’ escogido al azar.
Figura 14. Paso 3 del ejemplo de Prim
Paso 4: Ahora se tienen en cuenta las aristas desde B y F ya
que las demás están marcadas, la menor es: B E. Se
marca el nodo E y ahora el peso es = 25
Figura 11. Grafo inicial del ejemplo de Prim
Paso 1: Al considerar todos los vértices adyacentes a D, se concluye
que la arista de A D es la más corta, por lo tanto se selecciona y
se marca el nodo A. El peso hasta aquí es = 5.
Figura 15. Paso 4 del ejemplo de Prim
Paso 5: La arista de menor peso es: E C. Entonces se
marca el vértice C. El costo es = 30
Figura 12. Paso 1 del ejemplo de Prim
Paso 2: El próximo nodo a seleccionar es aquel que tenga
menor peso, desde D o desde A, hay que estos dos ya están
marcados. Por lo tanto se elige la arista: D F. Se marca el
vértice F. El peso ahora es = 11. Figura 16. Paso 5 del ejemplo de Prim
Paso 6: La única opción que queda es: E G, ya que los
demás ya está marcados. En verde está marcado el árbol de
expansión mínima de este nodo:
Figura 13. Paso 2 del ejemplo de Prim
6
AGRADECIMIENTOS
Queremos agradecer al profesor Francisco Alejandro Medina
por orientarnos durante todo este semestre y por motivarnos a
la investigación de las diferentes estructuras de datos que nos
servirán en nuestra carrera profesional y en el campo laboral,
para que sepamos identificar de manera eficaz y rápida cual
de todas será más óptima.
REFERENCIAS
Figura 17. Paso 6 del ejemplo de Prim
Referencias de páginas web
2.4 Codido de Prim C++
[1]. Latexnine. Aplicaciones de Dijkstra. Disponible:
const int INF = 1000000;
int cn;
[Link]
vector< vector > ady; //Lista de adyacencia ones-de-dijkstra
[2]. Wikipedia. Algoritmo de Prim.
[Link]
vector< vector > Grafo :: prim(){ m#C.C3.B3digo_en_C.2B.2B
[3]. Monografías.
vector< vector > adyacencia = this->ady;
[Link]
vector< vector > arbol(cn);
vector markedLines; ografia-algoritmo-prim/monografia-algoritmo-
vector :: iterator itVec; [Link]
[4]. [Link]
for(int i = 0; i < cn; i++) arbol[i] = vector (cn, INF); /04/[Link]
[5]. [Link]
int padre = 0;
[Link]/2011/07/algoritmo-de-
int hijo = 0;
while([Link]() + 1 < cn){ padre = hijo; [Link]
markedLines.push_back(padre);
for(int i = 0; i < cn; i++) adyacencia[i][padre] = INF;
int min = INF; for(itVec = [Link](); itVec !=
[Link]();
itVec++)
for(int i = 0; i < cn; i++) if(min > adyacencia[*itVec][i]){
min = adyacencia[*itVec][i];
padre = *itVec;
hijo = i;
}
arbol[padre][hijo] = min;
arbol[hijo][padre] = min;
}
return arbol;
}
CONCLUSIONES
• Para nosotros como estudiantes de Ingeniería de
Sistemas y Computación, comprendemos la importancia
de este tipo de algoritmos, ya que nos ayudaran en el
manejo de datos y optimización al manejar distancias y
lugares.
[2]. [Link]
[3]. [Link]
