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

Juan Carlos Yungán Cazar, Edgar Gualberto Salazar Álvarez, Jhon Eduardo Villacrés Sampedro

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.

Texto completo:

PDF HTML XML

Referencias


Bellman–Ford Algorithm | DP-23. (2012, diciembre 1). GeeksforGeeks. https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/

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

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

Moreno, E. (2012). Grafos: Fundamentos y Algoritmos. Santiago de Chile, Chile: Editorial ebooks Patagonia - J.C. Sáez Editor.

Recuperado de https://elibro.net/es/ereader/espoch/68438?page=82.

Mukhlif, F., & Saif, A. (s. f.). Comparative Study On Bellman-Ford And Dijkstra Algorithms. 6.

Patel, V. (2014). A survey paper of Bellman-ford algorithm and Dijkstra algorithm for finding shortest path in GIS application. 4(1), 3.

Pérez Aguila, R. (2013). Una introducción a las matemáticas discretas y teoría de grafos. El Cid Editor.

Recuperado de https://elibro.net/es/lc/espoch/titulos/36562

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

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.

Recuperado de: https://elibro.net/es/lc/espoch/titulos/53862

Rodríguez Villalobos, A. (2017). Grafos: software para la construcción, edición y análisis de grafos. Bubok Publishing S.L.

Recuperado de https://elibro.net/es/lc/espoch/titulos/55604

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

Singh, J. B., Tripathi, R. C., & Research, D. (2018). Investigation of Bellman–Ford Algorithm, Dijkstra’s Algorithm for suitability of SPP. 6(1), 4.

Skiena, S. S. (2008). The Algorithm Design Manual. Springer London. https://doi.org/10.1007/978-1-84800-070-4




DOI: https://doi.org/10.23857/pc.v7i7.4285

Enlaces de Referencia

  • Por el momento, no existen enlaces de referencia
';

Bookmark and Share




Polo del Conocimiento              

Revista Científico-Académica Multidisciplinaria

ISSN: 2550-682X

Casa Editora del Polo                                                 

Manta - Ecuador       

Dirección: Ciudadela El Palmar, II Etapa,  Manta - Manabí - Ecuador.

Código Postal: 130801

Teléfonos: 056051775/0991871420

Email: polodelconocimientorevista@gmail.com / director@polodelconocimiento.com

URL: https://www.polodelconocimiento.com/