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 do we need Dijkstra's Algorithm? We have seen that BFS can only be used to find the shortest path in unweighted graphs. So, for the weighted graphs, Dijkstra comes to our rescue. Dijkstra can be used for all 6 types of graphs. BUT, there is a scenario where DIJKSTRA's ALGORITHM CAN NOT BE USED : when a graph has a NEGATIVE CYCLE .  So a path is called a 'Negative Cycle' if: a) There is a cycle (quite obvious, isn't it ?) b) The Total weight of the cycle should be a negative number. For example - for now, let's consider in the above graph, the weight of edge AD as -6 instead of +6. Now, if we see the path DBAD, it is a cycle and total weight = 1 + 3 - 6 = -2, that is negative weight. So, a negative cycle. So, what is the reason that Dijkstra's Algorithm fails for a negative cycle? For one more time let's consider in the above graph the weight of edge AD as -6 instead of +6.  Now, we know Dijkstra finds the shortest path. If the graph has a negative...