Shortest Distance Graph Algorithms - How do they differ?
The shortest distance graph algorithms can be tricky. Which algorithm should be used when, whether it can work for negative edges or cycles, which one is the most efficient for the given problem - you should be asking these questions before deciding on a Shortest Distance Algorithms. The implementation and pseudo code for the standard Shortest Distance Algorithms are easily available on the web but how these different algorithms differ is often not highlighted. In this post, I will focus on how different graph algorithms differ from each other. These different algorithms differ in term of - Single Source Shortest Path vs All Pair Shortest Path Algorithms . Single Source Shortest Path algorithm calculates the shortest distance from a given Source vertex to all other graph vertices. All Pair Shortest Distance algorithm calculates the shortest distance between all pairs of graph vertices. Weighted graph - Can the algorithm work if edges have weights? Negative weight edges - Will