Shortest Path Algos

Djikshtra
// Single Source Shortest Path
Time Complexity(NlogN + ElogN) == (ElogN)
Space Complexity(N + M) = O(M)

//Doesn't Works for NEGATIVE EDGES
Why -> https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges
//In case of Dense Graph Time Complexity O(N^2)

Bellmon Ford
//N - 1 Iterations because Any shortest path cannot have more than N - 1 edges

// Single Source Shortest Path
Time Complexity(N*M)
Space Complexity O(M)
//Works for NEGATIVE EDGES
//But Not for NEGATIVE CYCLE
//WE CAN DETECT THE NEGATIVE CYCLE AND PATH


Floyd Warshall
//Time Complexity O(N^3)
Space Complexity O(N^2)
//IDEA - We take every vertice as the intermediate vertices b/w every pair
All Pair shortest path problem
//Works for NEGATIVE EDGES
//But Not for NEGATIVE CYCLE
//WE CAN DETECT THE NEGATIVE CYCLE