Single Source Shortest Path

Graph Type Algorithm Algorithm Gist 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(ElogV) 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(EV)

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