The Heap Space

  Single Source Shortest Path Algorithms BFS Dijkstra's Algorithm Bellman Ford Algorithm Time Complexity O(V^2) O(V^2) O(E.V) Space Complexity O(E) O(V) O(V) Limitation Does not work for weighted graphs in general. If all weight is same in weighted graph or can be made same, then it will work for weighted graph as well Works for weighted as well as unweighted graph. Does not work is there is a negative cycle in the graph. Not able to detect negative cycle. No limitation for working. Works for all kinds of graph as well as able to detect negative cycle in the graph. Only disadvantage is it's runtime complexity is highest here as compared to BFS, Dijkstra and Floyd Warshall Working for Unweighted Graph use this as it is easy to implement Avoid it as we have to implement a min heap too in this case which will slow this down Avoid it as Time Complexity is not good Working for Weighted Graph (no negative cycle) Not supported can be used Avoid it as Time Complexity is not good Workin...

    Why to use Bellman Ford Algorithm? We have seen earlier that both BFS and Dijkstra's algorithm can not be used when we have negative cycle in a graph. So, Bellman Ford Algorithm gives us a way to handle negative cycle in a graph. Remember, in any graph, if we have a negative cycle, we can't use any algorithm to find shortest path. Bellman Ford algorithm helps us to detect and notify the negative cycle in a graph, if present any.  In Bellman Ford Algorithm, our focus is gonna be on edges rather than vertices or nodes. To recall, in Dijkstra's Algorithm, our focus was on nodes. The Bellman Ford Algorithm runs for (V-1) times where V is the no. of vertices/nodes in the graph.In each iteration it go es through all edges and tries to find the optimal shortest distance. Why it runs (V-1) times, we will see to it later in this post. If there is a negative cycle present in graph, the Bellman Ford algorithm can detect it in Vth (V is the no. of vertices/nodes in the grap...