����������������������������������������������������������������������������������

 

Algoritmo de Bellman Ford para solucionar el problema de la ruta m�s corta entre nodos

 

Bellman Ford algorithm to solve the shortest path problem between nodes

 

Algoritmo de Bellman Ford para resolver o problema do caminho mais curto entre n�s

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Correspondencia: jyungan@espoch.edu.ec

 

 

Ciencias Tecnolog�as de la Informaci�n y la Comunicaci�n

Art�culo de Investigaci�n

��

* Recibido: 23 de mayo de 2022 *Aceptado: 12 de junio de 2022 * Publicado: 19 de julio de 2022

 

       I.          Mag�ster en Interconectividad de Redes, Ingeniero en Sistemas Inform�ticos, Escuela Superior Polit�cnica de Chimborazo, Riobamba, Ecuador.

      II.          Mag�ster en Matem�tica B�sica, Ingeniero en Sistemas, Escuela Superior Polit�cnica de Chimborazo. Riobamba, Ecuador.

    III.          M�ster Universitario en Tecnolog�a Educativa y Competencias Digitales, Mag�ster en Desarrollo de la Inteligencia y Educaci�n, Ingeniero en Sistemas, Escuela Superior Polit�cnica de Chimborazo, Riobamba, Ecuador.

Resumen

Conocer la historia de la ruta m�s corta es algo impredecible, ya que el problema del camino m�s corto se ha venido presentando desde la antig�edad, por ejemplo: encontrar caminos cortos hacia la comida. Es por ello que se consideraba un problema elemental y f�cil de resolver. A�os m�s tarde investigadores desarrollaron m�todos para dar una soluci�n independiente a problemas como: rutas con menos tr�fico, caminos en un laberinto, enrutamiento alternativo, llamadas a larga distancia, etc.). Su evoluci�n a dar soluciones ha permitido desarrollar m�todos matriciales para el camino m�s corto de longitud unitaria.� El m�todo Bellman-Ford permite encontrar la ruta m�s corta con un algoritmo m�s simple, maneja arcos negativos y su tiempo de ejecuci�n es menor, lo que le convierte en el m�todo a ser estudiado.

Palabras Clave: Bellman-Ford; Algoritmo; Ruta m�s corta.

 

Abstract

Knowing the history of the shortest route is somewhat unpredictable, since the problem of the shortest path has been present since ancient times, for example: finding short routes to food. That is why it was considered an elementary problem and easy to solve. Years later, researchers developed methods to provide an independent solution to problems such as: routes with less traffic, paths in a maze, alternative routing, long distance calls, etc.). Its evolution to provide solutions has allowed the development of matrix methods for the shortest path of unit length. The Bellman-Ford method allows finding the shortest path with a simpler algorithm, it handles negative arcs and its execution time is shorter, which makes it the method to be studied.

Keywords: Bellman-Ford; Algorithm; Shortest route.

 

Resumo

Conhecer a hist�ria do caminho mais curto � algo imprevis�vel, pois o problema do caminho mais curto est� presente desde a antiguidade, por exemplo: encontrar caminhos curtos para alimenta��o. Por isso era considerado um problema elementar e de f�cil solu��o. Anos depois, pesquisadores desenvolveram m�todos para fornecer uma solu��o independente para problemas como: rotas com menos tr�fego, caminhos em labirinto, roteamento alternativo, chamadas de longa dist�ncia etc.). Sua evolu��o para fornecer solu��es permitiu o desenvolvimento de m�todos matriciais para o caminho mais curto de comprimento unit�rio. O m�todo de Bellman-Ford permite encontrar o caminho mais curto com um algoritmo mais simples, trata arcos negativos e seu tempo de execu��o � menor, o que o torna o m�todo a ser estudado.

Palavras-chave: Bellman-Ford; Algoritmo; Rota mais curta.

����������������������������������������������������������������������������������������������

Introducci�n

Encontrar la ruta m�s corta, radica en hallar un camino entre un nodo origen y un nodo destino. Estos nodos se encuentran enlazados directa o indirectamente a trav�s de arcos que tienen una ponderaci�n, el cual puede ser entendido como costo, distancia, tiempo, etc. El algoritmo de Bellman Ford, soluciona el problema de la ruta m�s corta, empleando teor�a de grafos y an�lisis y dise�o de algoritmos. �

Es importante entender que un grafo es una dupla �compuesta por un conjunto finito �de v�rtices, tambi�n llamados nodos y t�picamente dibujados por c�rculos y un conjunto �que llamaremos conjunto de aristas. Mientras que, un algoritmo es una secuencia finita y ordenada de pasos para realizar una tarea en forma precisa.

Las redes de datos (grafos) utilizan protocolos para establecer comunicaci�n entre diferentes equipos denominados host. Estos protocolos (algoritmos) est�n gobernados por reglas que determinan su comportamiento. El enrutamiento de mensajes entre equipos (nodos/routers) se lo hace a trav�s de protocolos que garantizan la conectividad entre redes.

 

Desarrollo

La red (grafo) es un tipo com�n de estructura de datos que ofrece una visi�n hol�stica y descendente para dar sentido a diversos sistemas interactivos, incluidos los sistemas sociales, los sistemas biol�gicos, los sistemas de tr�fico, los sistemas de comunicaci�n, etc., que se ven muy afectados por una peque�a porci�n de nodos influyentes, tambi�n llamados propagadores influyentes. Dichos nodos desempe�an un papel fundamental y pueden enriquecer significativamente nuestra comprensi�n de los sistemas mencionados. Por ejemplo, ser capaces de detectar eficaz y adecuadamente los nodos influyentes nos permite controlar la propagaci�n de epidemias, dise�ar un plan de marketing v�lido, evitar que la red el�ctrica falle, predecir el flujo de tr�fico futuro e identificar prote�nas esenciales. (Liu et al., 2021)

Un grafo �est� formado por dos conjuntos

• �, un conjunto de v�rtices (tambi�n llamados nodos)
• �, un conjunto de aristas (cada arista est� asociada a dos v�rtices).

En las situaciones de modelizaci�n, las aristas se utilizan para expresar alg�n tipo de relaci�n entre los v�rtices. (Pruim, s. f.)

La teor�a de grafos proporciona un lenguaje para hablar de las propiedades de las relaciones. Dise�ar algoritmos de grafos realmente novedosos es una tarea muy dif�cil. La clave para utilizar eficazmente los algoritmos de grafos en las aplicaciones reside en modelar correctamente el problema para poder aprovechar los algoritmos existentes. Familiarizarse con muchos problemas algor�tmicos de grafos diferentes es m�s importante que entender los detalles de los algoritmos de grafos particulares. (Skiena, 2008)

 

La ruta m�s corta

Si tenemos dos v�rtices en un grafo y m�ltiples caminos entre ellos, entonces hay un camino m�s corto en esa colecci�n. Ese camino no es necesariamente �nico. El problema del camino m�s corto es el proceso de encontrar el camino m�s corto entre dos v�rtices de un grafo. Podemos considerarlo como la ruta m�s eficiente a trav�s del grafo.

Otra forma de considerar el problema del camino m�s corto es recordar que un camino es una serie de relaciones derivadas. El camino m�s corto es la serie con la derivaci�n m�s corta, o la relaci�n m�s cercana. Dado que un grafo modela relaciones, a menudo nos interesan las relaciones m�s cercanas. (Shortest Path Problem - an overview | ScienceDirect Topics, s. f.)

El problema de la ruta m�s corta es uno de los problemas de optimizaci�n de redes m�s fundamentales. Este problema surge en la pr�ctica y surge como un subproblema en muchos algoritmos de optimizaci�n de redes. (Cherkassky et al., 1996)�

 

Algoritmos b�sicos

Los algoritmos m�s importantes para resolver los problemas de camino m�s corto son:

• La b�squeda de amplitud y la b�squeda de profundidad se refieren a diferentes �rdenes de b�squeda; para la b�squeda de profundidad, se pueden encontrar casos en los que su implementaci�n ingenua no encuentra una soluci�n �ptima, o no termina.

• El algoritmo de Dijkstra resuelve el problema del camino m�s corto de una sola fuente si todos los pesos de las aristas son mayores o iguales a cero. Sin empeorar la complejidad del tiempo de ejecuci�n, este algoritmo puede, de hecho, calcular los caminos m�s cortos desde un punto de partida s dado a todos los dem�s nodos.
• El algoritmo de Bellman-Ford tambi�n resuelve el problema de los caminos m�s cortos de una sola fuente, pero a diferencia del algoritmo de Dijkstra, los pesos de las aristas pueden ser negativos.
• El algoritmo de Floyd-Warshall resuelve el problema de las rutas m�s cortas de todos los pares.
• El algoritmo A* resuelve el problema del camino m�s corto de una sola fuente para costes de aristas no negativos. (Shortest Path Problem - an overview | ScienceDirect Topics, s. f.)

 

M�todo

La elecci�n del m�todo m�s adecuado y su correcta ejecuci�n es lo que impulsa a realizar una buena investigaci�n. Para el presente trabajo se ha considerado el m�todo mixto (cualitativo y cuantitativo), ya que se est� contemplado:

1. Se har� uso de las t�cnicas documentales y de experimento. La t�cnica documental para la recolecci�n de informaci�n a trav�s de publicaciones en revistas cient�ficas. La t�cnica del experimento con el uso del programa para el an�lisis de grafos.
2. El An�lisis y aplicaci�n paso a paso del algoritmo de Bellman Ford se la realiza en una hoja de trabajo (Tabla 1)
3. An�lisis y dise�o de un programa escrito en Java que permita implementar el algoritmo de Bellman Ford.

 

An�lisis

Algoritmo de Bellman-Ford

Este algoritmo busca la estructura del grafo y genera la mejor soluci�n. Resuelve el problema del camino m�s corto de fuente �nica en el que los pesos de los bordes pueden ser negativos. El algoritmo de Bellman-Ford para las rutas m�s cortas es casi completamente intuitivo y devuelve un valor booleano que indica si hay o no un ciclo de peso negativo al que se puede acceder desde la fuente. Entonces, cuando hay un ciclo, el algoritmo indica que no existe una soluci�n, pero cuando no la hay, el algoritmo produce los caminos m�s cortos y su peso. Adem�s, la base es la siguiente: dado un gr�fico con �v�rtices, la mayor cantidad de arcos que puede haber en un camino m�s corto es . Esto se demuestra f�cilmente por inducci�n. El camino m�s corto tiene m�s de , entonces debe tener un circuito negativo, de manera similar, un gr�fico con un circuito negativo tendr� un camino m�s corto de n o m�s arcos. Todas estas observaciones conducen al algoritmo Bellman-Ford. (Mukhlif & Saif, s. f.) (Figura 1)

 

 

 

 

 

 

Figura 1: Proceso del algoritmo de Bellman Ford

Fuente:� (Patel, 2014)

 

 

Pseudoc�digo del algoritmo Bellman-Ford

1. Inicialice todos los v�rtices y establezca su distancia desde la fuente a un valor alto, como infinito, y establezca el valor de distancia para la fuente en 0 valores
2. Repita lo siguiente para el n�mero de �tiempos tales como: para cada arista �que pertenece al gr�fico dibujado si distancia�entonces la , lo que significa que la distancia se actualiza.
3. Repita los siguientes pasos para cada borde �que pertenece al gr�fico dibujado si �entonces no existe ning�n ciclo negativo - peso entre el origen y el destino.
4. Devuelve los valores de distancia para todos los nodos una vez completadas todas las iteraciones. (Mukhlif & Saif, s. f.)

 

Funcionamiento

�Al igual que otros problemas de programaci�n din�mica, el algoritmo calcula las rutas m�s cortas de forma ascendente. Primero calcula las distancias m�s cortas que tienen como m�ximo un borde en la ruta. Luego, calcula los caminos m�s cortos con 2 aristas como m�ximo, y as� sucesivamente. Despu�s de la i-�sima iteraci�n del bucle exterior, se calculan los caminos m�s cortos con como m�ximo i aristas. Puede haber un m�ximo de |V| � 1 aristas en cualquier camino simple, por eso el ciclo externo ejecuta |v| - 1 vez. La idea es, asumiendo que no hay un ciclo de peso negativo, si hemos calculado las rutas m�s cortas con como m�ximo aristas i, entonces una iteraci�n sobre todas las aristas garantiza dar la ruta m�s corta con aristas como m�ximo (i+1). (�Bellman�Ford Algorithm | DP-23�, 2012)

Este algoritmo tiene las ventajas de:

• Minimizaci�n de costes.
• Maximizaci�n del rendimiento.
• Permite dividir el tr�fico.

Desventajas:

• En el protocolo de enrutamiento no se tiene en cuenta las ponderaciones.
• Respuesta lenta a los cambios en la topolog�a de red. (Singh et al., 2018)

 

Dise�o de clases: (Figura 2:)

Figura 2: Diagrama de clases

Fuente: Juan C. Yung�n-Cazar.

 

 

Implementaci�n del programa

Clase Vertex: En esta clase se implementa los nodos. Est� compuesta por los atributos nombre, estado de visitado, lista de aristas asociadas a los nodos, distancia m�nima, y nodo antecesor. (Figura 3)

 

Figura 3: Implementaci�n clase Vertex (Nodo)

Fuente: Juan C. Yung�n-Cazar.

Clase Edge: En esta clase se implementa las aristas que conectan a los nodos. Est� compuesta por los atributos ponderaci�n o peso; referencia de nodo inicial y referencia de nodo final. (Figura 4)

 

Figura 4: Implementaci�n clase Edge (Arista)

Fuente: Juan C. Yung�n-Cazar.

 

Clase BellmanFord: En esta clase se impelenta el algorirmo de Bellman Ford. Est� compuesta por los atributos lista de nodos (vertexList) y lista de aristas (edgexList). (Figura 5)

 

Figura 5: Implementaci�n clase BellmanFord

Fuente: Juan C. Yung�n-Cazar.

 

Escenario de aplicaci�n

Se dise�a un grafo dirigido con 9 nodos que representan a diferentes ciudades del pa�s y las aristas representan a las conexiones viales entre ellas con su respectiva distancia. (Figura 6)

Figura 6: Escenario propuesto

Fuente: Juan C. Yung�n-Cazar.

 

Clase App: En esta clase se implementa el escenario de estudio. (Figura 7)

Figura 7: Implementaci�n clase App (Escenario de pruebas)

Fuente: Juan C. Yung�n-Cazar.

 

 

 

Resultados

 

Tabla 1: Resultados del an�lisis y aplicaci�n paso a paso del algoritmo

 

Tabla 2: Resultados de rutas m�nimas calculadas por el programa

 

El camino m�s corto calculado por el algoritmo tomando como nodo origen Quito hasta el nodo destino Macas es el que visita los nodos: Latacunga con una ponderaci�n de 109 Km, Ambato (40 Km) con una ponderaci�n acumulada de 149 Km, Riobamba (61 Km) con una ponderaci�n acumulada de 210 Km; hasta llegar al nodo destino Macas (157 Km) con una ponderaci�n total de 367 Km.

El siguiente camino m�s corto calculado por el algoritmo tomando como nodo origen Quito hasta el nodo destino Macas es el que visita los nodos: Latacunga con una ponderaci�n de 109 Km, Ambato (40 Km) con una ponderaci�n acumulada de 149 Km, Puyo (102 Km) con una ponderaci�n acumulada de 251 Km; hasta llegar al nodo destino Macas (126 Km) con una ponderaci�n total de 377 Km.

El camino m�s largo calculado por el algoritmo tomando como nodo origen Quito hasta el nodo destino Macas es el que visita los nodos: Nueva Loja con una ponderaci�n de 255 Km, Francisco de Orellana (82 Km) con una ponderaci�n acumulada de 337 Km, Tena (174 Km) con una ponderaci�n acumulada 511 Km, Puyo (74 Km) con una ponderaci�n acumulada de 585 Km; hasta llegar al nodo destino Macas (126 Km) con una ponderaci�n total de 711 Km.

 

Conclusiones

Un grafo es una representaci�n gr�fica de nodos (ciudades, routers) conectados por arcos (carreteras, enlaces seriales)

La ruta m�nima o camino m�s corto simplemente es la distancia entre nodos (origen y destino) con menor distancia.

El problema del camino m�s corto es recordar que un camino es una serie de relaciones derivadas. El camino m�s corto es la serie con la derivaci�n m�s corta o la relaci�n m�s cercana. Dado que un gr�fico est� modelando relaciones, a menudo nos interesan las relaciones m�s cercanas.

El algoritmo de Bellman Ford plantea una soluci�n al problema de la ruta m�s corta, pero no es el �nico, por ejemplo, para resolver este problema tambi�n existe el algoritmo de Dijkstra.

El tiempo de ejecuci�n del algoritmo de Bellman Ford es bajo (microsegundos) lo que le convierte en un m�todo muy eficiente para un peque�o n�mero de nodos.

Encontrar la ruta m�s corta, por lo general es un problema frecuente en temas de log�stica y transporte, las redes de comunicaci�n de datos; entre las m�s importantes.

�reas del conocimiento involucrada: Teor�a de grafos, An�lisis y dise�o de algoritmos, Estructura de datos, Algebra lineal, Log�stica y transporte, Redes de computadoras, etc. �

 

Referencias

1. Bellman�Ford Algorithm | DP-23. (2012, diciembre 1). GeeksforGeeks. https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
2. Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73(2), 129-174. https://doi.org/10.1007/BF02592101
3. Liu, Y., Wei, X., Chen, W., Hu, L., & He, Z. (2021). A graph-traversal approach to identify influential nodes in a network. Patterns, 2(9), 100321. https://doi.org/10.1016/j.patter.2021.100321
4. Moreno, E. (2012). Grafos: Fundamentos y Algoritmos. Santiago de Chile, Chile: Editorial ebooks Patagonia - J.C. S�ez Editor.
5. Recuperado de https://elibro.net/es/ereader/espoch/68438?page=82.
6. Mukhlif, F., & Saif, A. (s. f.). Comparative Study On Bellman-Ford And Dijkstra Algorithms. 6.
7. Patel, V. (2014). A survey paper of Bellman-ford algorithm and Dijkstra algorithm for finding shortest path in GIS application. 4(1), 3.
8. P�rez Aguila, R. (2013). Una introducci�n a las matem�ticas discretas y teor�a de grafos. El Cid Editor.
9. Recuperado de https://elibro.net/es/lc/espoch/titulos/36562
10. Pruim, R. (s. f.). 1 Introduction to Graphs | Graphs. Recuperado 27 de junio de 2022, de https://rpruim.github.io/m252/S19/from-class/graphs/introduction-to-graphs.html#graphs
11. Reid, A. y Lorenz, J. (2018). Introducci�n al enrutamiento y la conmutaci�n en la empresa: gu�a de estudio de CCNA Discovery. Pearson Educaci�n.
12. Recuperado de: https://elibro.net/es/lc/espoch/titulos/53862
13. Rodr�guez Villalobos, A. (2017). Grafos: software para la construcci�n, edici�n y an�lisis de grafos. Bubok Publishing S.L.
14. Recuperado de https://elibro.net/es/lc/espoch/titulos/55604
15. Shortest Path Problem�An overview | ScienceDirect Topics. (s. f.). Recuperado 27 de junio de 2022, de https://www.sciencedirect.com/topics/computer-science/shortest-path-problem
16. Singh, J. B., Tripathi, R. C., & Research, D. (2018). Investigation of Bellman�Ford Algorithm, Dijkstra�s Algorithm for suitability of SPP. 6(1), 4.
17. Skiena, S. S. (2008). The Algorithm Design Manual. Springer London. https://doi.org/10.1007/978-1-84800-070-4

 

 

 

� 2022 por los autores. Este art�culo es de acceso abierto y distribuido seg�n los t�rminos y condiciones de la licencia Creative Commons Atribuci�n-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0)

(https://creativecommons.org/licenses/by-nc-sa/4.0/).