Contenido
1. INTRODUCION .................................................................................................... 2
a. Objetivo del informe ......................................................................................... 2
b. Importancia de los algoritmos a implementar .............................................. 2
c. Breve descripción del problema a resolver. ................................................... 2
2. FUNDAMENTOS TEÓRICOS ............................................................................. 3
a. Concepto de grafos y teoría de caminos más cortos .................................... 3
b. Explicación de los algoritmos implementados .............................................. 4
i. Algoritmo de Dijkstra ................................................................................... 4
ii. Algoritmo de Floyd-Warshall ...................................................................... 4
c. Aplicaciones prácticas del algoritmo .............................................................. 5
i. Redes de Transporte ...................................................................................... 5
ii. Optimización de Rutas de Transporte Público ......................................... 6
iii. Análisis de Redes Económicas y Globales ............................................. 6
iv. Inteligencia Artificial y Modelado de Redes Sociales ........................... 7
3. METODOLOGIA ................................................ ¡Error! Marcador no definido.
a. Explicación detallada del código. .................................................................... 7
b. Entrada y salida esperada del programa. .................................................... 17
c. Capturas de pantalla o ejemplos de ejecución. ........................................... 18
4. REFERENCIAS..................................................................................................... 22
1. INTRODUCION
a. Objetivo del informe
El propósito de este informe es analizar e implementar dos algoritmos
fundamentales para la resolución del problema de caminos más cortos en grafos:
Dijkstra y Floyd-Warshall. Estos algoritmos son ampliamente utilizados en
diversas aplicaciones del mundo real, como la optimización de rutas en sistemas
de navegación, la gestión eficiente de redes de telecomunicaciones y la
planificación de infraestructuras.
El informe detallará cómo funcionan estos algoritmos, sus diferencias y su
aplicabilidad en distintos escenarios. Además, se incluirá una implementación
práctica utilizando JavaScript, HTML y CSS, permitiendo visualizar gráficamente
los resultados de los cálculos. A través de esta implementación, se evaluará el
rendimiento de cada algoritmo y se comparará su eficiencia en términos de
complejidad computacional y tiempos de ejecución.
Este análisis tiene el objetivo de ofrecer una comprensión clara y práctica del
problema, brindando una base teórica y experimental que permita su aplicación
en diversas áreas tecnológicas.
b. Importancia de los algoritmos a implementar
Los algoritmos de búsqueda de caminos óptimos son fundamentales en diversas
aplicaciones como la planificación de rutas, redes de comunicación y gestión del
tráfico urbano. Con el crecimiento de las ciudades y el aumento del tráfico,
encontrar rutas óptimas es esencial para minimizar tiempos de viaje y mejorar la
eficiencia operativa en sistemas de transporte.
Los sistemas de navegación, como Google Maps o Waze, emplean versiones
optimizadas de Dijkstra y Floyd-Warshall para proporcionar rutas eficientes a los
usuarios en tiempo real. En telecomunicaciones, estos algoritmos se utilizan para
la optimización de redes y la gestión del tráfico de datos, asegurando una
distribución equitativa de los recursos de comunicación. En robótica y
automatización, permiten a los robots planificar trayectorias óptimas en entornos
dinámicos, mejorando la navegación autónoma y reduciendo el consumo
energético.
c. Breve descripción del problema a resolver.
El problema que se busca resolver es encontrar la ruta más corta entre nodos en
un grafo dirigido y ponderado, lo que es útil en sistemas de navegación y análisis
de redes. En particular, se implementará un sistema interactivo en el que los
usuarios puedan agregar nodos y aristas, asignar pesos y calcular la mejor ruta
entre dos puntos utilizando los algoritmos mencionados.
Uno de los desafíos clave es la representación eficiente del grafo, ya que
diferentes estructuras de datos afectan el rendimiento de los algoritmos. Se
evaluará el impacto de la implementación en la escalabilidad y eficiencia de los
cálculos, comparando el desempeño de Dijkstra en grafos de gran tamaño frente
a Floyd-Warshall en escenarios donde se requiere la matriz de caminos más
cortos entre todos los nodos.
2. FUNDAMENTOS TEÓRICOS
a. Concepto de grafos y teoría de caminos más cortos
Los grafos son una estructura matemática que se utiliza para modelar relaciones
entre objetos. Un grafo está compuesto por un conjunto de nodos (también
llamados vértices) y un conjunto de aristas que los conectan. Las aristas pueden
ser dirigidas o no dirigidas, y pueden tener pesos asociados que representan
costos, distancias o tiempos.
El estudio de los caminos más cortos en grafos es un área fundamental en la teoría
de grafos y algoritmos. Los problemas de caminos más cortos buscan determinar
la secuencia de nodos más eficiente entre un nodo origen y un nodo destino,
minimizando una función de costo.
Existen diversas representaciones de grafos, entre las más utilizadas están:
• Lista de adyacencia: Se representa cada nodo con una lista de sus vecinos
adyacentes. Es eficiente en términos de memoria y se usa comúnmente en
grafos dispersos.
• Matriz de adyacencia: Usa una matriz bidimensional donde la entrada (i,
j) indica la presencia y el peso de una arista entre los nodos i y j. Es útil
para grafos densos, pero consume más memoria.
Los problemas de caminos más cortos tienen aplicaciones en múltiples áreas
como redes de telecomunicaciones, logística y planificación de rutas. Diferentes
algoritmos resuelven este problema con diversas eficiencias y aplicaciones
específicas.
Uno de los algoritmos más conocidos para este problema es el de Dijkstra, que
encuentra la ruta más corta desde un nodo origen hasta todos los demás nodos
en un grafo con pesos no negativos. Este algoritmo es ampliamente utilizado en
sistemas de navegación y redes de comunicación.
Por otro lado, el algoritmo de Floyd-Warshall es una técnica de programación
dinámica que encuentra las rutas más cortas entre todos los pares de nodos en
un grafo ponderado. Es útil cuando se requiere conocer todas las combinaciones
de caminos y se utiliza en redes de telecomunicaciones y análisis de redes
sociales.
La elección del algoritmo depende de la estructura del grafo y del problema
específico a resolver. En aplicaciones en tiempo real, como los sistemas de
navegación, se prefieren versiones optimizadas de Dijkstra, mientras que en
análisis de redes, donde se requiere una matriz completa de caminos, Floyd-
Warshall es más adecuado.
b. Explicación de los algoritmos implementados
i. Algoritmo de Dijkstra
El algoritmo de Dijkstra encuentra la ruta más corta desde un nodo origen a todos
los demás nodos en un grafo con pesos no negativos. Funciona manteniendo un
conjunto de distancias mínimas desde el nodo origen hasta cada nodo y
utilizando una estructura de cola de prioridad para seleccionar el nodo con la
menor distancia conocida.
Su complejidad computacional en su implementación básica es O(V²), donde V
es el número de nodos. Sin embargo, si se usa una cola de prioridad basada en
montículos binarios (como el heap de Fibonacci), la complejidad mejora a
O((V+E) log V), donde E es el número de aristas. Esta reducción en la complejidad
es crucial para grafos grandes, ya que mejora significativamente el tiempo de
ejecución. En términos prácticos, esto significa que a medida que aumenta la
cantidad de nodos y conexiones, la eficiencia del algoritmo sigue siendo
manejable y no crece exponencialmente.
ii. Algoritmo de Floyd-Warshall
El algoritmo de Floyd-Warshall es un método basado en programación dinámica
que permite calcular las rutas más cortas entre todos los pares de nodos en un
grafo ponderado. Su funcionamiento se basa en una matriz de distancias que se
actualiza iterativamente considerando cada nodo como un posible intermediario
en los caminos.
La complejidad computacional de este algoritmo es O(V³), lo que significa que el
tiempo de ejecución crece cúbicamente con respecto al número de nodos. Esto
hace que Floyd-Warshall sea menos eficiente en grafos grandes en comparación
con Dijkstra. Sin embargo, su ventaja radica en su simplicidad y en que permite
obtener la matriz de distancias entre todos los pares de nodos en una sola
ejecución, algo que no es posible con Dijkstra sin múltiples ejecuciones.
En términos de aplicabilidad, Floyd-Warshall se utiliza cuando se necesita
conocer todas las distancias entre pares de nodos, como en redes de
telecomunicaciones y análisis de tráfico en ciudades. En cambio, Dijkstra es
preferido en escenarios donde solo se necesita encontrar la ruta más corta desde
un nodo específico.
c. Aplicaciones prácticas del algoritmo
i. Redes de Transporte
En el estudio de Amenah Sufyan y Amenah [1], se aborda la creciente
problemática de la congestión del tráfico urbano, exacerbada por el aumento
poblacional y el incremento del número de vehículos. Las consecuencias incluyen
no solo demoras significativas y pérdidas económicas, sino también un aumento
en las emisiones de CO2 y accidentes de tráfico, con más de un millón de muertes
anuales reportadas por la OMS.
Como solución, se propone una mejora del algoritmo de Dijkstra, que incorpora
datos en tiempo real de OpenStreetMap y el simulador SUMO (Simulation of
Urban Mobility). Esta versión optimizada permite evaluar el nivel de congestión
en las carreteras y redirigir vehículos para evitar atascos, lo que resulta en una
reducción del 23% en el número de vehículos congestionados y una disminución
del 15% en el consumo de combustible. Además, las emisiones de CO2 se reducen
en un 14%.
El estudio resalta la urgencia de implementar tecnologías innovadoras para
mejorar la movilidad urbana y sugiere que futuros trabajos se enfoquen en
sistemas de guiado de rutas, en los que la comunicación entre vehículos y la
infraestructura puede jugar un papel crucial para aliviar la congestión.
ii. Optimización de Rutas de Transporte Público
En el estudio de Chen [2], se centra en el algoritmo de Dijkstra, propuesto en
1959, que es uno de los más clásicos para resolver este tipo de problemas. El
algoritmo funciona mediante una técnica de búsqueda por anchura y un enfoque
codicioso, evaluando todos los nodos del grafo y seleccionando el camino óptimo
en cada paso. También se explora la implementación de un sistema de consulta
de rutas de autobús en la ciudad de Walnut, aplicando el algoritmo de Dijkstra
para optimizar el transporte público. Este sistema ayuda a los residentes a
encontrar la ruta más corta desde una estación de autobús de inicio hasta una de
destino, ahorrando tiempo en sus desplazamientos.
Además, se identifican algunas limitaciones del algoritmo, como su eficiencia en
ciudades más grandes con rutas de autobús más complejas, sugiriendo áreas
futuras de investigación para mejorar la aplicabilidad de Dijkstra en contextos
más complicados.
iii. Análisis de Redes Económicas y Globales
Xing y Li [3] En este estudio se aborda la optimización de los caminos de
transferencia de bienes intermedios en las redes de Valor Global (GVC) mediante
una revisión del algoritmo de Floyd-Warshall. Se critica que estudios anteriores
no consideraron la longitud de la cadena de valor, lo que afectaba su validez. Se
introduce el concepto de Longitud de Ruta de Relevancia Fuerte (SRPL), que
cuantifica cómo las relaciones interindustriales influyen en el costo de
transacciones a lo largo de los procesos de producción.
El estudio propone que la transferencia eficiente de bienes intermedios es
proporcional a las relaciones de insumo-producto (IO) y se ve afectada
negativamente por la longitud del proceso de valor agregado. Además, se
emplean medidas derivadas para identificar ventajas comparativas en las
cadenas de valor global, permitiendo así la formulación de políticas comerciales
más efectivas.
A través de simulaciones y el uso de indicadores basados en SRPL, se puede
evaluar la fortaleza de las relaciones intersectoriales. Estas innovaciones
permiten una comprensión más profunda de la estructura dinámica de las
cadenas de suministro, superando las limitaciones de enfoques previos. Este
enfoque ofrece una forma más precisa de modelar las interacciones económicas
entre sectores.
iv. Inteligencia Artificial y Modelado de Redes Sociales
Ortega et al. [4], aborda el problema de cómo identificar y analizar la red de
colaboración científica entre autores en el ámbito de la psicología social. Se
observa que, a pesar de la simplificación de las relaciones sociales, las cadenas de
colaboración entre investigadores a menudo superan los seis eslabones, lo que
complica la visualización de estas conexiones. La necesidad de una metodología
efectiva es crucial para entender el grado de colaboración entre los autores y la
productividad de sus investigaciones.
Para abordar este problema, se propone el uso del algoritmo de Floyd, que busca
encontrar el camino más corto entre pares de nodos en un grafo. Este algoritmo
permite calcular las distancias mínimas de colaboración entre autores, facilitando
así la identificación de "Small Worlds", o grupos de coautoría compactos, que
reflejan la estructura de colaboración en el campo. A través de este enfoque, se
analiza una base de datos de 8,091 autores, seleccionando y conectando a los 15
autores más prolíficos de una revista específica. La investigación no solo
proporciona un panorama global de las interacciones científicas, sino que
también ofrece información cualitativa sobre los autores y sus interrelaciones,
contribuyendo a una mejor comprensión de la dinámica de la colaboración en la
ciencia.
3. METODOLOGÍA
a. Descripción del lenguaje de programación y librerías
utilizadas
b. Representación del grafo
c. Estructura del código y funciones principales.
4. IMPLEMETACION
a. Explicación detallada del código.
El código desarrollado está implementado en JavaScript, con una interfaz
gráfica en HTML5 y CSS3. Se basa en el uso de la API de Canvas para la
representación visual del grafo, permitiendo la interacción dinámica del
usuario.
• Obtención del Contexto de Canvas y Variables Globales
Se obtiene el elemento de canvas con el id graphCanvas desde el DOM,
que es donde se dibujarán los nodos y las aristas.
✓ nodes: Array que almacenará los nodos del grafo, cada nodo es un
objeto con las propiedades x, y (coordenadas) y name (nombre del
nodo).
✓ edges: Array que almacenará las aristas, cada arista tiene un
origen, destino, peso y si es o no no dirigida.
✓ operation: Variable que guardará la operación actual que el
usuario está realizando (agregar nodo, agregar arista, etc.).
✓ selectedNode: Guarda el nodo que está seleccionado actualmente,
si existe, cuando se agregan aristas.
• Configuración de la Operación Actual
Esta función se utiliza para establecer qué operación va a realizar el
usuario. Por ejemplo, si está en modo de agregar un nodo o una arista.
Resetea selectedNode cada vez que se cambia de operación.
• Manejo del click en el canvas para agregar nodos/aristas o removerlos
Dependiendo del valor de operation, el clic realiza diferentes acciones:
✓ Agregar un nodo: Si la operación es add_node, solicita al usuario
el nombre del nodo y lo añade en las coordenadas clickeadas.
✓ Agregar una arista dirigida: Si la operación es add_edge, se
conecta el nodo seleccionado previamente con el nodo clickeado,
pidiendo un peso para la arista.
✓ Agregar una arista no dirigida: Si la operación es
add_edge_undirected, se agregan dos aristas: una de from a to y
otra de to a from con el mismo peso.
✓ Eliminar un nodo o arista: Si la operación es remove, elimina el
nodo o la arista clickeada
• Función para Obtener Nodo Cercano al Clic
Esta función toma las coordenadas (x, y) y verifica si el clic está cerca de
algún nodo (dentro de un radio de 20 píxeles). Utiliza [Link]() para
calcular la distancia euclidiana entre el clic y el nodo.
• Función para Obtener Arista Cercana al Clic
Determina si se hizo click cerca de alguna arista (para eliminarla)
• Función para Dibujar una Flecha (Arista)
✓ Se utiliza un algoritmo geométrico para crear una flecha
compuesta por un "cuerpo" (tallo) y una "cabeza" (punta).
✓ Los parámetros from y to son los nodos de origen y destino de la
flecha, y color define el color de la flecha (puede ser rojo o negro
dependiendo si es parte de un camino resaltado).
✓ Calcula las coordenadas necesarias para los vértices del polígono
que representa la flecha.
• Función para Dibujar el Grafo Completo
Esta función se encarga de dibujar todo el grafo en el canvas:
✓ Primero, limpia el canvas con [Link]() para eliminar cualquier
contenido previo.
✓ Luego, dibuja todas las aristas y nodos.
✓ Si una arista está en el camino resaltado (highlightedPath), la dibuja
en rojo.
✓ Finalmente, dibuja los nodos con un círculo y su nombre.
• Solicitar los Nombres de los Nodos Fuente y Destino, busca los Nodos
Fuente y Destino en el Grafo
Se solicita al usuario que ingrese el nombre del nodo fuente (el punto de
inicio) y el nombre del nodo destino (el punto final) mediante cuadros de
diálogo. Seguidamente se buscan los nodos en el array nodes utilizando
el nombre que el usuario proporcionó. Si el nodo no se encuentra, las
variables source o target serán undefined.
• Verificar que los Nodos Existentes sean Válidos
Si alguno de los nodos (source o target) no es válido (no se encuentra en
el grafo), se muestra un mensaje de error usando SweetAlert y la función
termina sin ejecutar más código.
• Inicializar las Estructuras de Datos para Dijkstra, Inicializar las
Distancias y la Cola de Prioridad
✓ dist: Un objeto que guarda la distancia más corta conocida desde
el nodo fuente a cada nodo del grafo.
✓ prev: Un objeto que guarda el nodo previo de cada nodo en el
camino más corto (usado para reconstruir el camino).
✓ pq: Una cola de prioridad mínima que se usará para obtener el
nodo con la distancia más corta en cada iteración.
✓ Para cada nodo, se inicializan las distancias en infinito (lo que
indica que no hay un camino conocido).
✓ Se inicializan los valores previos de cada nodo en null.
✓ Se inserta cada nodo en la cola de prioridad con una distancia
inicial de infinito.
✓ La distancia del nodo fuente se establece en 0 (ya que la distancia
al nodo fuente es cero) y se actualiza en la cola de prioridad.
• Algoritmo de Dijkstra
✓ El algoritmo entra en un bucle que continúa mientras la cola de
prioridad no esté vacía.
✓ u = [Link](): Extrae el nodo con la distancia más corta (el
nodo más cercano al origen).
✓ Si u es el nodo destino (target), el algoritmo termina, ya que se
encontró el camino más corto.
✓ Luego, se exploran todas las aristas que parten del nodo u.
• Mostrar el Camino Más Corto y su Distancia
✓ Si se encontró un camino, se reconstruye el camino de las aristas
que componen el camino más corto. Para ello, se recorren los
nodos del camino y se encuentra la arista correspondiente entre
cada par de nodos.
✓ Luego, se dibuja el grafo resaltando las aristas que forman parte
del camino más corto.
✓ Finalmente, se muestra un resumen del resultado.
✓ El camino más corto se muestra en formato de texto (con flechas
→ entre los nodos).
✓ La distancia total del camino más corto se muestra en una etiqueta
de badge.
• Inicialización de Variables y Ejecución de Dijkstra para Cada Nodo
Fuente
Se obtiene el número total de nodos en el grafo mediante [Link].
dMatrix es un array que almacenará las distancias mínimas entre todos
los pares de nodos en el grafo, representadas en forma de una matriz.
✓ Se recorre cada nodo del grafo, tratándolo como el nodo fuente (a
través del índice i).
✓ dist es un objeto que mantiene las distancias mínimas conocidas
desde el nodo fuente a todos los demás nodos.
✓ Se inicializan todas las distancias en infinito, excepto la distancia
del nodo fuente que se establece en 0.
✓ pq es una cola de prioridad mínima que se utiliza para aplicar el
algoritmo de Dijkstra. Los nodos se insertan en esta cola con sus
distancias iniciales.
• Ejecución del Algoritmo de Dijkstra
Se ejecuta el algoritmo de Dijkstra con la cola de prioridad:
✓ Mientras la cola no esté vacía, se extrae el nodo u con la menor
distancia conocida.
✓ Se iteran todas las aristas edge que parten de u.
✓ Para cada arista, se calcula una distancia alternativa (alt) sumando
la distancia del nodo u y el peso de la arista.
✓ Si la distancia alternativa alt es menor que la distancia conocida al
nodo de destino [Link], se actualiza la distancia y se ajusta
la prioridad del nodo en la cola.
• Construcción de la Matriz de Distancias y la creación de la tabla HTLM
para mostrar la matriz
✓ Se construye una tabla HTML para representar la matriz de
distancias dMatrix de manera visual.
✓ Se agrega una cabecera a la tabla con los nombres de los nodos.
✓ Luego, por cada nodo, se agrega una fila con las distancias desde
ese nodo a todos los demás.
✓ Si una distancia es infinita (lo que significa que no hay un camino
directo entre dos nodos), se muestra el símbolo "∞".
✓ Finalmente, la tabla se inserta en el div con id output, para que se
muestre en la interfaz.
b. Entrada y salida esperada del programa.
• Entrada Dijkstra
• Salida Dijkstra
• Entrada Floyd
• Salida Floyd
c. Capturas de pantalla o ejemplos de ejecución.
• Interfaz de Usuario
Aquí tenemos todas las opciones de insertar nodo, agregar arista (dirigido o
no dirigido), eliminar, y ejecutar ya sea en Dijktra o Floyd.
• Ingreso de nodos
Damos clic en el botón ingresar nodo y luego en el lienzo se ingresa los
nodos con su respectivo nombre.
• Ingreso de aristas
Para esto damos clic en ingresar arista ya sea dirigida o no dirigida y
seleccionamos un nodo inicial y otro final y se le agrega el valor.
• Para eliminar nodos damos clic en el botón eliminar y de ahí al nodo que
deseamos eliminar.
• Para ejecutar el programa Dijktra
Palcular la ruta más corta usando Dijkstra le damos clic en el botón
Ejecutar Dijkstra y nos pedirá ingresar el nodo inicial y el final una vez hecho
esto en el lienzo nos mostrará la ruta más corta cambiando las aristas a
color rojo y mostrando el resultado en la parte inferior.
• Matriz de distancia
Para mostrar el cuadro de matriz de distancia de Dijkstra le damos clic al
botón de matriz de distancia y nos saldrá un cuadro con los datos.
• Para ejecutar el programa en Floyd
Le damos clic en el botón ejecutar Floyd y nos saldrá el resultado tanto
como las interacciones que se realizaron, la matriz final, los caminos más
cortos y la excentricidad de nodos.
5. REFERENCIAS
[1] M. T. Amenah Sufyan and S. Amenah, “Optimizing Dijkstra’s Algorithm
for Managing Urban Traffic Using Simulation of Urban Mobility (Sumo)
Software,” Ann. Math. Phys., vol. 7, no. 2, pp. 206–213, 2024, doi:
10.17352/amp.000124.
[2] R. Chen, “Dijkstra’s Shortest Path Algorithm and Its Application on Bus
Routing,” Proc. 2022 Int. Conf. Urban Plan. Reg. Econ. 2022）, vol. 654, no.
Upre, pp. 321–325, 2022, doi: 10.2991/aebmr.k.220502.058.
[3] L. Xing and Y. Li, “Revised Floyd-Warshall Algorithm to Find Optimal
Path in Similarity-Weight Network and Its Application in the Analysis of
Global Value Chain,” J. Phys. Conf. Ser., vol. 1298, no. 1, pp. 0–6, 2019, doi:
10.1088/1742-6596/1298/1/012010.
[4] M. P. Ortega, R. L. Serrano, E. Q. Vidal, and J. J. L. García, “Los «small
worlds» y el algoritmo de Floyd: Una manera de estudiar la colaboración
científica,” Psicothema, vol. 18, no. 1, pp. 78–83, 2006.
