ALGORITMO DIJKSTRA

(Informe de laboratorio)

Cristhian Julian Garcia Gil Codigo: 701694

cuando se debe usar una única interfaz
[email protected]
multipunto para interconectar varios sitios,

Resumen: Para entender el proceso por

el cual realizaremos la aplicación del
código DIJKSTRA, empezaremos realizar
un camino por toda Colombia en el cual
nuestro principal objetivo será tomar un
origen y un destino delimitando el camino
mas corto, para lo cual realizaremos un
grafo con la aplicación de Matlab, en
donde trazremos el camino mas corto
que nos puede calcular el programa Durante la ejecución del algoritmo, iremos
dando un segmento con pasos mas marcando cada nodo con su mínima
distancia al nodo C (nuestro nodo elegido).
cortos y que el peso sea menor.
Para el nodo C, esta distancia es 0. Para el
resto de nodos, como todavía no
l Introducción
conocemos esa distancia mínima, empieza
También llamado algoritmo de caminos
siendo infinita (∞):
mínimos, es un algoritmo para la
determinación del camino más corto dado
un vértice origen 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.
es un modelo que se clasifica dentro de los
algoritmos de búsqueda. Su objetivo, es
determinar la ruta más corta, desde el nodo
origen, hasta cualquier nodo de la red. Su
También tendremos un nodo actual .
metodología se basa en iteraciones, de
Inicialmente, el nodo actual será C (nuestro
manera tal que en la práctica, su desarrollo
nodo elegido). En la imagen, marcaremos el
se dificulta a medida que el tamaño de la
nodo actual con un punto rojo.
red aumenta, dejándolo en clara
desventaja, frente a métodos de
Ahora, revisaremos los vecinos de nuestro
optimización basados en programación
nodo actual (A, B y D) en cualquier orden.
matemática.
Empecemos con B. Sumamos la mínima
distancia del nodo actual (en este caso, 0)
El algoritmo de Dijkstra te permite calcular
con el peso de la arista que conecta al nodo
la ruta más corta entre un nodo (tú eliges
actual con B (en este caso, 7), y obtenemos
cuál) y todos los demás nodos en el grafo .
0 + 7 = 7. Comparamos ese valor con la
Encontrarás una descripción del algoritmo
mínima distancia de B (infinito); el valor más
al final de esta página, pero ¡vamos a
pequeño es el que queda como la distancia
estudiarlo con un ejemplo explicado!
mínima de B (en este caso, 7 es menos que
Calcularemos la distancia más corta entre
infinito):
el nodo C y los demás nodos del grafo:
 ll Montaje experimental

Para el montaje y desrrollo de nuestro

trabajo realizamos como lo comentamos
anteior mente un camino por nuestro pais en
donde el principal objetivo sera llegar por el
camino mas corto calculado por Matlab

Bien. Ahora revisaremos al vecino A.

Sumamos 0 (la distancia mínima de C,
nuestro nodo actual) con 1 (el peso de la
arista que conecta nuestro nodo actual con
A) para obtener 1. Comparamos ese 1 con
la mínima distancia de A (infinito) y
dejamos el menor valor:

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; Para la configuración de mi grafo se genero
cuando se obtiene el camino más corto la siguiente ruta la cual fue aleatoria según
desde el vértice origen, al resto de vértices la instrucción
que componen el grafo, el algoritmo se
detiene. El algoritmo es una especialización
de la búsqueda de costo uniforme, y como
tal, no funciona en grafos con aristas de
coste negativo (al elegir siempre el nodo
con distancia menor, pueden quedar
excluidos de la búsqueda nodos que en
próximas iteraciones bajarían el costo
general del camino al pasar por una arista
con costo negativo).
Una vez teniendo la ruta podemos diseñar names={'1' '2' '3' '4' '5' '6' '7' '8' '9' '10' '11'
el código correspondiente con el aplicativo '12' '13' '14' '15' '16' '17' '18' '19' '20' '21'};
MATLAB el cual según el calculo G = graph(s,t,weights,names)
realizado daremos el grafo correspondiente plot(G,'EdgeLabel',G.Edges.Weight)
para nuestra rura. CMV=shortestpath(G,16,21);
highlight(plot(G,'EdgeLabel',G.Edges.Weight
),CMV,'EdgeColor','red')

Con el código de Matlab podemos encontrar

el orden aleatorio que nos arrojó el
aplicativo.

Si le damos zoom para validar la ruta

obtenida del camino mas coto tenemos

Realizamos el cálculo y diseño

correspondiente en Matlab dándole los
pares de números en el orden según el
Excel.

Una suma total de 62+63+52 dando el coste

menor y una ruta acorde.

III Análisis de resultados

Preguntas:

¿Qué algoritmos se emplean para calcular

el camino más corto?,
R/ Es un algoritmo greddy

Para poder resolver un problema usando el

Señalamos con una línea roja el camino enfoque greedy, tendremos que considerar
correspondiente que nos arroja el aplicativo ,6 elementos:
con la configuración ingresada
1. Conjunto de candidatos (elementos
s=[1 1 2 2 4 5 5 8 5 4 6 14 8 9 10 10 12 10 seleccionables).
10 12 11 11 12 13 14 14 16 17 17 20 19 20] 2. Solución parcial (candidatos
t=[2 6 5 4 6 3 8 9 9 9 9 9 14 13 6 13 13 12 seleccionados).
11 11 7 18 19 17 15 16 17 20 19 19 21 21] 3. Función de selección (determina el
weights=[23 45 30 63 64 52 27 71 70 3 69 mejor candidato del conjunto de
39 64 39 15 14 16 12 49 16 79 35 70 53 74 candidatos seleccionables).
38 62 79 63 20 52 50 ] 4. Función de factibilidad (determina si
 es posible completar la solución IV conclusiones
parcial para alcanzar una solución
del problema). • La idea subyacente en este
5. Criterio que define lo que es una algoritmo consiste en ir explorando
solución (indica si la solución parcial todos los caminos más cortos que
obtenida resuelve el problema). parten del vértice origen y que llevan
6. Función objetivo (valor de la a todos los demás vértices; cuando
solución alcanzada). se obtiene el camino más corto
desde el vértice origen hasta el resto
Algoritmo Floyd-Warshall de los vértices que componen el
grafo, el algoritmo se detiene.
es un algoritmo de análisis sobre grafos
para encontrar el camino mínimo en grafos • Una de sus aplicaciones más
dirigidos ponderados. El algoritmo importantes reside en el campo de la
encuentra el camino entre todos los pares telemática. Gracias a él, es posible
de vértices en una única ejecución. El resolver grafos con muchos nodos,
algoritmo de Floyd-Warshall es un ejemplo lo que sería muy complicado
de programación dinámica resolver sin dicho algoritmo,
encontrando así las rutas más cortas
El algoritmo de Warshall es un ejemplo de entre un origen y todos los destinos
algoritmo booleano. A partir de una tabla en una red.
inicial compuesta de 0`s (no hay
correspondencia inicial en el grafo) y 1`s • En múltiples aplicaciones donde se
(hay una correspondencia, llamase “flecha”, aplican los grafos, es necesario
entre nodos), obtiene una nueva matriz conocer el camino de menor costo
denominada “Matriz de Clausura Transitiva” entre dos vértices dados:
en la que se muestran todas las posibles
uniones entre nodos, directa o Distribución de productos a una red
indirectamente. Es decir, si de “A” a “B” no de establecimientos comerciales.
hay una “flecha”, es posible que si haya de Distribución de correos postales.
“A” a “C” y luego de “C” a “B”. Luego, este Sea G = (V, A) un grafo dirigido
resultado se verá volcado en la matriz final. ponderado. El problema del camino
más corto de un vértice a otro
El algoritmo de Floyd-Warshall compara consiste en determinar el camino de
todos los posibles caminos a través del menor costo, desde un vértice u a
grafo entre cada par de vértices. El otro vértice v. El costo de un camino
algoritmo es capaz de hacer esto con sólo es la suma de los costos (pesos) de
{\displaystyle V^{3}}{\displaystyle V^{3}} los arcos que lo conforman.
comparaciones (esto es notable
considerando que puede haber hasta
{\displaystyle V^{2}}{\displaystyle V^{2}}
aristas en el grafo, y que cada combinación
de aristas se prueba). Lo hace mejorando
paulatinamente una estimación del camino
más corto entre dos vértices, hasta que se
sabe que la estimación es óptima.