TIME COMPLEXITY ANALYSIS OF SINGLE SOURCE SHORTEST PATH (SSSP) ALGORITHMS

There are real-world complex networks formed by people, roads, communication network nodes, genes, file Servers and financial transactions etc based on their interdependent associations. Often, there exist multiple paths to connect one of the network nodes to another in the networks. Various situations demand shortest path to reach from one node to another. To find shortest path between a pair of the nodes is challenging in terms of computational cost, therefore, competing algorithms for Shortest Path problem are analyzed to predict their greediness for the computing resources such as memory, bandwidth, or hardware but most often its computational time. The scope of this work is to provide comprehensive knowledge on single-source shortest path problem and analyze time complexity of the prominent single-source shortest path algorithms.