Complexity Analysis of Graph-Based Algorithms for Large-Scale Network Optimization

Abstract

This paper presents a comprehensive complexity analysis and empirical evaluation of graph-based algorithms applied to large-scale network optimization. Nine classical algorithms, including Dijkstra’s, A*, Bellman-Ford, Floyd-Warshall, Johnson’s, Prim’s, Kruskal’s, Edmonds-Karp, and Push-Relabel, were analyzed across various network scales (1K to 1M nodes) using synthetically generated graphs. Key performance metrics such as runtime, memory consumption, and scalability were assessed under realistic conditions. The results show that Dijkstra, A*, Prim, and Kruskal offer excellent scalability and efficiency for sparse, large-scale networks, while Floyd-Warshall and Johnson’s algorithms are constrained by memory and computational overhead. In flow optimization, Push-Relabel outperformed Edmonds-Karp on dense graphs but exhibited higher memory usage. Mathematical modeling using curve fitting confirmed theoretical complexity trends and enabled runtime prediction for larger, untested networks. Based on these findings, we provide practical algorithm selection guidelines tailored to network size, density, and optimization objective. This study bridges theoretical insights and practical deployment, offering a data-driven foundation for choosing optimal algorithms in domains such as transportation, communication, and infrastructure systems.