Corporación Universitaria Minuto de Dios - UNIMINUTO

Facultad de Ingeniería
Ingeniería de Sistemas
Matemáticas Discretas
Actividad 6

Implementación de Algoritmos

Introducción
Resuelvan el siguiente ejercicio, empleando los diferentes algoritmos que orienten a la
representación de grafos ponderados, lista de adyacencias, funciones proposicionales haciendo
uso de Dijkstra. Recuerde que, en esta orientación, el objetivo del grupo es buscar el camino
mas corto como a su vez interpretar estos datos a partir de cuantificadores lógicos y funciones
proposicionales.

1. Al tener presente la siguiente red, donde su origen es la ciudad de Bogotá, deberán hallar y
solucionar con su respectivo paso a paso los puntos que se presentan a continuación:
 Fuente: elaboración propia.

a. ¿A cuáles nodos se puede llegar desde el nodo Bogotá?

Desde Bogotá se puede llegar a los nodos de Tunja, Medellín, Caracas, Leticia, Lima y Cali.

b. Coloquen las etiquetas correspondientes e identifiquen el estado del nodo si este es

Los permanentes son los de color amarillo y los temporales los que no tienen color.
Adicional el peso del nodo “I” está en metros, pero los demás están en Kilómetros, por lo
que el peso de “I” al convertir en Kilómetros queda: 794/1000 = 0.794 km
Vértice 1 2 3 4 5 6 7 8 9
A (0,A) (2898,F) (3845,G) (∞,H) (∞,I)
B (1234,A) (1542,D)
C (115,A) (115,A)
D (800,C) (800,C)
E (∞,A) (1276,D) (1276,D)
F (805,A) (2093,E) (2093,E)
G (837,A) (3008,F) (3008,F)
H (∞,A) (3662,G) (3662,G)
I (4204,H) (4204,H)
J (∞,A) (4204.79,I) (4204.79,I)

c. Evalúen las salidas que se pueden dar desde el nodo Medellin y asignen etiquetas a estos
nodos si son temporales o permanentes incluyendo su peso.
Desde Medellín (E) se tiene 3 salidas que son:
 Medellín - Barranquilla (D) con peso de 476 (Permanente)
 Medellín - Caracas (F) con peso de 817 (Temporales)
 Medellín - Bogotá (A) es infinito no tiene peso determinado (Temporales)
Dentro de estos 3 nodos se observa como permanente el nodo Barranquilla (D) que tiene la
distancia más corta y los nodos Caracas (F) y Bogotá (A) quedan como temporales.

Vértice 1 2 3 4 5 6 7 8 9
A (∞,E) (1276,C) (1276,C) (2569,G) (∞,H) (∞,J)
B (1218,D) (2510,A)
C (1161,D) (1161,D)
D (476,E) (476,E)
E (0,E)
F (817,E) (2081,A) (817,E)
G (2113,A) (1732,F) (1732,F)
H (∞,A) (2386,G) (2386,G)
I (2928,H) (2928,H)
 J (∞,A) (2928.79,I) (2928.79,I)
d. Evalúen las salidas que se dan desde el nodo Caracas y asignen etiquetas a estos nodos si
son temporales o permanentes incluyendo su peso.
Desde Caracas (F) se tiene 3 salidas que son
 Caracas - Medellín (E) con peso de 817 (Temporales)
 Caracas - Bogotá (A) con peso de 805 (Permanente)
 Caracas - Leticia (G) con peso de 915 (Temporales)
Dentro de estos 3 nodos se observa como permanente el nodo Bogotá (B) que tiene la
distancia más corta y los nodos Medellín (E) y Leticia(G) quedan como temporales.
Vértice 1 2 3 4 5 6 7 8 9 10
A (805,F) (805,F) (∞,E) (1752,G) (∞,H) (∞,J)
B (2039,A) (2347,D)
C (920,A) (920,A)
D (1605,C) (1605,C)
E (817,F) (∞,A) (2081,D) (2081,D)
F (0,F) (2898,E) (0,F)
G (915,F) (1642,A) (915,F) (915,F)
H (∞,A) (1569,G) (1569,G)
I (2111,H) (2111,H)
J (∞,A) (2111.79,I) (2111.79,I)

e. Evalúen las salidas que se dan desde el nodo Barranquilla y asignen etiquetas a estos nodos si
son temporales o permanentes incluyendo su peso.
Desde Barranquilla (D) se tiene 3 salidas que son
 Barranquilla – Panamá (B) con peso de 742 (Temporales)
 Barranquilla - Tunja (C) con peso de 685 (Temporales)
 Barranquilla - Medellín (E) con peso de 476 (Permanente)
Dentro de estos 3 nodos se observa como permanente el nodo Medellín (E) que tiene la
distancia más corta y los nodos Panamá (B) y Tunja (C) quedan como temporales.

Vertice 1 2 3 4 5 6 7 8
A (∞,E) (2098,F) (2098,F) (∞,H) (∞,J)
B (742,B) (3332,A)
C (685,D)
D (0,D)
E (476,D) (476,D) (∞,A)
F (1293,E) (1293,E) (3850,G)
G (2208,F) (2935,A) (2935,A)
H (∞,A) (3589,G) (3589,G)
I (4131,H) (4131,H)
J (∞,A) (4131.79,I) (4131.79,I)
f. Entreguen una conclusión general y una para cada ítem propuesto, donde interpreten cada
dato y hagan comprender a un lector que no conozca del tema, la explicación respectiva
para que logre una noción de este tema.
Sobre el ejercicio anterior, la gráfica representa las rutas de una carretera en un mapa,
donde cada nodo o punto de la red representa una ciudad, y las líneas que conectan cada
nodo es la carretera con un valor de la distancia que debe recorrer siendo también las
longitudes de las carreteras.
El objetivo del ejercicio es usar el algoritmo de Dijkstra para recorrer el camino de la forma
más optima con la menor distancia posible, eligiendo las distancias más cortas para pasar
de un nodo al otro, evaluando todas las posibilidades del nodo, dejando nodos marcados
como temporales, para luego de analizar la ruta más optima y corta, se convierte en nodo
permanente, del cual se parte para el siguiente nodo, y así sucesivamente hasta llegar al
punto final del trayecto. Esta información es crucial en la planificación de rutas y logística,
especialmente en el contexto de transporte y comunicaciones.
En este ejercicio evaluando las distancias de salida de Medellín (E), Caracas (F) y
Barranquilla (D) podemos concluir que:

 Las salidas de Medellín ofrecen rutas relativamente cortas hacia importantes nodos
como Bogotá y Barranquilla, siendo Medellín un nodo central con buenas
conexiones en términos de distancia y acceso.
 Las salidas desde Caracas son bastante largas en comparación con las otras,
indicando que Caracas está más aislada en términos de distancia relativa a los otros
nodos importantes. Sin embargo, aún mantiene conexiones directas significativas.
 Las salidas desde Barranquilla, al igual que Medellín, está bien conectada con otros nodos
clave, lo que la convierte en un importante punto de conexión en la red. Las distancias a
otros nodos como Ciudad de Panamá y Bogotá son competitivas, siendo un eje importante
en la red.

No olvide que las fórmulas las pueden encontrar en cualquier sitio de la web como libros,
artículos etc., pero como futuros ingenieros deben darse a comprender en su ámbito de
desarrollo. ¡Buena suerte!
Tomado de:
Ingeniería Industrial Online (2019). Algoritmo de Dijkstra.
[Link]
dijkstra/

Adaptado por:
Diego Andrés Beltrán Saavedra