iNFORME FINAL INVESTIGACION DE OPERACIONES

Algoritmo de Dijkstra & Floyd - Warshall

10 DE FEBRERO DE 2025
Roger aguilar frisancho
JOSE LUIS LOAYZA NARVAEZ
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.........................................4
i. Redes de Transporte...............................................................4
ii. Optimización de Rutas de Transporte Público........................5
iii. Análisis de Redes Económicas y Globales............................5
iv. Inteligencia Artificial y Modelado de Redes Sociales..........6
3. METODOLOGÍA.............................................................................6
a. Descripción del lenguaje de programación y librerías utilizadas
6
b. Representación del grafo...........................................................7
c. Estructura del código y funciones principales...........................7
4. IMPLEMETACION.........................................................................8
a. Explicación detallada del código................................................8
b. Entrada y salida esperada del programa.................................17
c. Capturas de pantalla o ejemplos de ejecución.........................18
5. Conclusiones y Recomendaciones...............................................23
a. Resumen de los resultados obtenidos......................................23
b. Posibles mejoras en la implementación...................................23
6. REFERENCIAS............................................................................23
 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
El desarrollo de la aplicación se realizó utilizando JavaScript como
lenguaje de programación principal, junto con HTML5 y CSS3 para la
interfaz gráfica. Se implementaron las siguientes tecnologías y librerías:

 JavaScript (ES6+): Utilizado para la lógica del grafo, la ejecución

de los algoritmos de Dijkstra y Floyd-Warshall, y la manipulación del
DOM.

 HTML5 y CSS3: Para la estructura y diseño de la interfaz gráfica,

permitiendo la interacción dinámica con los usuarios.

 Canvas API: Usada para la representación gráfica del grafo,

permitiendo el dibujo de nodos y aristas.

 SweetAlert2: Biblioteca para mejorar la experiencia del usuario con

cuadros de diálogo amigables.
  [Link]: Utilizado para mostrar la matriz de distancias de
Floyd-Warshall de manera ordenada y estructurada.

 [Link]: Librería que optimiza la implementación del algoritmo de

Dijkstra mediante una cola de prioridad basada en un heap binario.

b. Representación del grafo

El grafo se representa mediante dos estructuras de datos principales:

1. Lista de adyacencia: Se almacena cada nodo con un conjunto

de vecinos y los pesos de las aristas que los conectan.
let graph = {
"A": { "B": 2, "C": 5 },
"B": { "C": 1, "D": 4 },
"C": { "D": 3 },
"D": {}
};
2. Matriz de adyacencia: Se utiliza para el algoritmo de Floyd-
Warshall, donde se mantiene una matriz dist[][] donde dist[i][j]
almacena el peso de la arista entre el nodo i y el nodo j, o ∞ si
no hay conexión.
let dist = [
[0, 2, 5, ∞],
[∞, 0, 1, 4],
[∞, ∞, 0, 3],
[∞, ∞, ∞, 0]
];

c. Estructura del código y funciones principales.

El código se divide en módulos bien organizados:

1. Interfaz gráfica (HTML + CSS)

o Contiene un canvas donde se dibuja el grafo.

o Botones para agregar nodos, aristas y ejecutar los algoritmos.

2. Manejo del grafo

o addNode(name): Agrega un nodo al grafo.

o addEdge(from, to, weight): Agrega una arista dirigida o no

dirigida.

o removeNode(name): Elimina un nodo y sus aristas asociadas.

o removeEdge(from, to): Elimina una arista específica.

3. Algoritmos

o dijkstra(source, target): Calcula la ruta más corta desde un

nodo origen hasta un destino utilizando una cola de prioridad.
 o floydWarshall(): Calcula todas las rutas más cortas entre todos
los nodos, almacenándolas en una matriz de distancias.

4. Visualización

o drawGraph(): Dibuja el grafo en el canvas.

o highlightPath(path): Resalta la ruta más corta encontrada en

color rojo.

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. Conclusiones y Recomendaciones

a. Resumen de los resultados obtenidos

La implementación de los algoritmos de Dijkstra y Floyd-Warshall permitió
analizar y resolver el problema de encontrar caminos más cortos en grafos
dirigidos y ponderados. A través de la representación visual interactiva, se
logró comprobar que Dijkstra es más eficiente para consultas individuales
desde un nodo origen, mientras que Floyd-Warshall es más adecuado para
calcular todas las rutas posibles entre pares de nodos.

El uso de JavaScript, junto con HTML5 y CSS3, permitió desarrollar una

interfaz gráfica intuitiva, facilitando la manipulación del grafo mediante la
API de Canvas. La integración de estructuras de datos eficientes, como
listas de adyacencia y colas de prioridad, optimizó la ejecución de los
algoritmos. Se observó que Dijkstra con heap binario reduce el tiempo de
cómputo en comparación con la versión tradicional de O(V²). En contraste,
Floyd-Warshall, con O(V³) de complejidad, mostró limitaciones en grafos
grandes, pero proporcionó una visión global de todas las rutas posibles.

b. Posibles mejoras en la implementación

 Permitir la importación y exportación de grafos en formatos estándar
como JSON o CSV.
 Agregar funcionalidad para mover nodos dinámicamente dentro del
lienzo.
 Mejorar la visualización de rutas resaltadas con animaciones.
 Integrar soporte para grafos dinámicos, donde se puedan modificar
pesos en tiempo real.

6. 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.