Time Complexity on Single Source Shortest Path Algorithms
Published:
Graph data-structure is widely used represent different aspects in computer science (e.g., road network). We can denote the graph as \(G = (V, E)\), where \(V\) represents the set of vertices (in the context of road network it represents the intersections), and \(E\) represents the set of edges (in the context of road network it represents the road segments). Generally we define \(n~(= |V|)\) is the number of vertices and \(m~(= |E|)\) the number of edges to express the time and space complexity for algorithms related to graphs. One such problem is single-source shortest path (SSSP) that used to find the shortest path from a single node to all other nodes. For decades, Dijkstra’s algorithm has been the go-to method to solve this problem. The runtime of Dijkstra’s algorithm depends on the priority queue implementation and often has complexity of \(O(m + n \log n)\). Read more