Sanjay Mehta
Independent Researcher
India
Abstract
This manuscript presents a detailed performance analysis of Dijkstra’s shortest-path algorithm versus the Bellman-Ford algorithm within the context of network routing, using evaluation metrics such as computation time, memory usage, convergence behavior, and resilience to dynamic topology changes. Two representative routing scenarios are considered: a static wired network employing link-state routing protocols (e.g., OSPF) for Dijkstra’s algorithm, and a dynamic mobile ad hoc network (MANET) using distance-vector routing protocols (e.g., AODV) for Bellman-Ford. Simulation experiments were conducted on topologies ranging from 50 to 1,000 nodes, with link costs modeled according to real-world traffic traces available up to 2015. Results demonstrate that while Dijkstra’s algorithm outperforms Bellman-Ford in convergence speed and memory efficiency in static environments, Bellman-Ford exhibits superior adaptability in highly dynamic topologies despite higher computational overhead. Implications for protocol selection in engineering designs are discussed, and recommendations provided for scenarios where hybrid or hierarchical routing strategies may yield optimal performance.
Keywords
Dijkstra’s algorithm, Bellman-Ford algorithm, network routing, performance analysis, link-state, distance-vector
References
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90.
Bellman, R. (1957). Dynamic programming. Princeton University Press.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. Princeton University Press.
Huitema, C. (1995). Routing in the Internet (2nd ed.). Prentice Hall.
Johnson, D. B., & Maltz, D. A. (1996). Dynamic source routing in ad hoc wireless networks. Mobile Computing, 353–382.
Perkins, C. E., & Royer, E. M. (1999). Ad-hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (pp. 90–100).
Moy, J. (1998). OSPF version 2. RFC 2328.
Ns-2 Consortium. (2008). The NS Manual (Version 2.35). Retrieved from https://www.isi.edu/nsnam/ns/
Feofiloff, P., & Vieira, L. F. M. (2012). Comparative analysis of Dijkstra and Bellman-Ford algorithms in VANET environments. In Proceedings of the 6th International Conference on Broadband Communications, Networks and Systems (pp. 1–7).
