PRESENTACI N OPERACIONES

ALGORITMO DE FLOYD
PROGRAMACIÓN LINEAL
APLICACIÓN A UN CONTEXTO

Docente: Maryori

Lilia Gutiérrez Díaz
Rosangelie Plata Baleta
1

EJERCICIO PROPUESTO
Movilización de un lugar a otro
Lilia Gutiérrezse dispone a ir desde
su residencia en la calle 36 # 37-26
Edificio Estrella del prado hasta la
catedral de La Sagrada Familia
donde por motivo de una ceremonia
eucarística la espera su amigaRosangelie Plata.
Para cumplir su fin debe tomar en
cuenta diversas calles que le
proponen distintas rutas de llegada.
2

EJERCICIO PROPUESTO
Movilización de un lugar a otro
Es de gran importancia quellegue lo más puntual posible a la
catedral, pero está retrasada. Teniendo en cuenta esto, ella necesita
llegar en el menor tiempo posible, su objetivo es encontrar la ruta
más corta para llegar desde sucasa hasta la Catedral de La
Sagrada Familia.

3

PRESENTACIÓN DE
LA RED

4

PRESENTACIÓN DE LA RED

 La Red es dirigida, ya que
contiene arcos Dirigidos.
 La Red consta de 27 nodos o
vértices.
Los
arcos
Dirigidos
representan las calles de una
sola vía.

5

RED

Nodos y Arcos

RED

Nodos, Arcos y Distancias

7

PROBLEMAS DE RUTA MÁS
CORTA

Algoritmo de Dijkstra
Algoritmo FloydProgramación Lineal

ALGORITMO DE DIJKSTRA
Aplicación

Uso de la herramienta TORA para el desarrollo
del ejercicio.

9

ALGORITMO DE DIJKSTRA
Distancias de nodo a nodo

ALGORITMO DE DIJKSTRA
Algunas Iteraciones(1 y 2)

ALGORITMO DE DIJKSTRA
Algunas Iteraciones (26 y 27)

ALGORITMO DE DIJKSTRA
Posibles rutas de llegada

ALGORITMO DE DIJKSTRA
Solución ruta más corta

ALGORITMO DE
DIJKSTRA
Análisis de lasolución

Para que Lilia llegue a tiempo a la ceremonia
eucarística desde su casa en la calle 36 #3726 Edificio Estrella del Prado hasta la Catedral
de La Sagrada Familia, deberá tomar la ruta
máscorta la cual toma los nodos:
0-1-4-6-7-10-13-16-18-19-22-25-26
con
una distancia de 2045 metros.

ALGORITMO DE DIJKSTRA
Análisis de la solución

Ruta más corta: 0-1-4-6-7-10-13-16-18-19-22-25-26...