Single Source Shortest Path

Graph Type Algorithm Main Idea Data Structure Used Time Complexity
Unweighted Graph Breadth First Search (BFS) Explore each adjacent node before moving to next level(s) Queue O ( E + V )
Directed Acyclic Graph (DAG) (positive and negative edge weights) Topological Sorting and Bellman Ford Edge relaxation in topological order Stack O ( E + V )
Directed Graph with only positive edge weights Dijkstra’s Algorithm
C++ / Java : Extract the closest node(extract min) stored in a set / priority queue. O(VlogV), for each neighbor relax the edge and update the heap. O ( E log V ) Heap O((E+V)logV)
Directed Graph with positive and negative edge weights Bellman Ford For all the nodes (V), relax all the edges (E) List O ( E . V )

Copyright (c) 2019-2023,
All rights reserved.