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 the algorithm work if there are negative weight edges?
  • Negative weight cycles - The shortest distance problem is not defined for a graph with a negative weight cycle. Because you can keep on going around that cycle and distance with keep on getting smaller. So no algorithms will work in this case.(Update - as pointed out on Reddit, although Shortest Distance problem is not well defined if there are negative weight cycles, it is slightly incorrect to say that algorithms do not work in this case. e.g. Bellman Ford algorithm can be used to detect negative weight cycles in graphs). 
  • Space and Time Complexity
Now let's look at the standard algorithms from these aspects.

Breadth First Search

  • Single Source Shortest Path algorithm
  • Does not work for weighted graphs. All edges should have equal or unit weight.
  • Does not work for Negative weight edges 
  • Time Complexity - O(E + V)
  • Space Complexity - O(V)

Dijkstra 

  • Single Source Shortest Path algorithm
  • Works well for Weighted graphs
  • Does not work for Negative weight edges 
  • Time Complexity -  O(E log(V) +  V log(V)) using standard heaps, O(E + V log(V)) using Fibonacci Heaps. 
  • Space Complexity - O(V)
  • Single Source Shortest Distance algorithm
  • Negative Edges - Yes
  • Time Complexity - O(EV)
  • Space Complexity - O(V)

Shortest Distance for Directed Acyclic Graphs(DAG)

Apparently if the graph is of type DAG (Directed Acyclic Graph), then there is another algorithm with better time complexity. It works for all cases where Bellman Ford works plus it has better time complexity. 
  • Single Source Shortest Distance algorithm
  • Negative Edges - Yes
  • Time Complexity - O(E + V)
  • Space Complexity - O(V)

Floyd Warshall 

  • All pairs shortest path algorithm
  • Works well for Weighted graphs
  • Works well with negative weight edges
  • Time Complexity - O(V^3)
  • Space Complexity - O(V^2)

Now let's try to use these differences to solve a problem. I was asked this problem in an interview and it is a very good problem to test understanding of different graph algorithms. 

You've always been intrigued with the Six Degrees of Kevin Bacon game. Let's say if two actors have been in the same movie we call them 'friends' and if two actors have not been in the same movie, we say they are not 'friends'. Now choose any two actors at random -- we want to calculate the number of degrees of separation and the path between them. How do you go about this problem?
• Discuss your algorithm ideas. For each algorithm talk about the trade-offs.

Ok. Clearly this is a shortest distance problem. 
  • What are the weights of the edges? All edges have unit weight. So BFS can be used. 
  • Are there negative weight edges? No. All edges have weight 1. So Dijkstra can also be used. Between BFS and Dijkstra, BFS has better Time complexity O (E + V) vs O(E + V log(V) ) in Dijkstra. Space complexity is same for both O(V). Clearly between BFS and Dijkstra, BFS is better in this case. 
  • This problem is best modeled as an undirected graph and can contain cycles. So DAG algorithm will not work.
  • But what about Floyd Warshall Algorithm. So do we need an All Pair Shortest Path algorithm here? Floyd warshall has time complexity of O(V^3) and space complexity of O(V^2) which is worse than BFS. Here we need to understand the problem better. Do we need to perform the distance calculation for a single pair of actors or there can be many looks we need to perform. If we need to do a one-off lookup, then clearly BFS is a better solution. However if we need to perform many lookups over a long period, then it make better sense to just run Floyd Warshal once, calculate all the distances and store the results and later use the stored result for each lookup.
Hope this articles helps you understand different shortest distance algorithms better. Please comment if you have any questions or feedback. 


Comments

Post a Comment

Popular posts from this blog

Prefer ThreadLocalRandom over Random

Java 7 has introduced a new random number generator - ThreadLocalRandom Normally to generate Random numbers, we either do Create an instance of java.util.Random  OR Math.random() - which internally creates an instance of java.util.Random on first invocation.  However in a concurrent applications usage of above leads to contention issues - Random is thread safe for use by multiple threads. But if multiple threads use the same instance of Random, the same seed is shared by multiple threads. It leads to contention between multiple threads and so to performance degradation.  ThreadLocalRandom is solution to above problem. ThreadLocalRandom has a Random instance per thread and safeguards against contention. From the api docs -  Usages of this class should typically be of the form:  ThreadLocalRandom.current().nextX(...)  (where  X  is  Int ,  Long , etc). When all usages are of this form, it is never possible to accidently share a  ThreadLocalRandom  across multiple thre
Read more

Java - One liner to Configure Logging

Often while writing some quick test or doing a prototype, we want to use logging. But we do not want to spend any time writing a properties file and doing the whole setup. However there is a quick way to get log4j ready to use in a single line. Log4j provides a BasicConfigurator which can be used to quickly configure the logging. Usage Example - public class LoggingOneLiner1 { private static final Logger logger = Logger .getLogger(LoggingOneLiner1.class); public static void main(String[] args) { // Configure the logging - this does the whole setup BasicConfigurator.configure(); // Optional Step - change the logging level to INFO from default DEBUG Logger.getRootLogger().setLevel(Level.INFO); logger.info("Its nice to to be able to configure logging in one line"); logger.debug("I like quick and dirty java tricks"); } } From the api docs of log4j - The invocation of the   BasicConfigurator.configure   method creates a rather simpl
Read more