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...

    What is All Pairs Shortest Path (APSP)?  It calculates the shortest distance between each pair of vertices/nodes of the graph. We can also implement APSP by BFS, Dijkstra's Algorithm and Bellman-Ford Algorithm by running these algorithms for all the vertices/nodes in the graph/ Here we will be discussing a new algorithm for calculating only All Pairs Shortest Path. That means it can't be used to find the Single Source Shortest Path. The name of the algorithm is the  Floyd Warshall Algorithm.  The Floyd Warshall Algorithm does not work for / detects a negative cycle. Floyd Warshall Algorithm [Time Complexity: O(V^3) ,  Space Complexity: O(V^2) ] 1. Initialize a square matrix (adjacency matrix):          a. If i==j , put 0 in that cell          b. Else if there is a direct edge from node i to node j then we put the weight of that edge in that cell.          c. Else if there is no ...