Shortest path algorithm

You might have searched for different routes between two locations in google maps, but have you ever  thought about how would they do this ? finding all those small junctions and even tracking traffic in real time. Sounds crazy !!

Computer Science will have answer to each and every question !! The above scenario can be done with graphs. Say we find all the junction in the map and put those in a graph vertex. now we need to find the shortest path between 2 nodes. We are Done !!. One more application of the same will be in networking finding the shortest path to reach from one computer to another.

In the above image if i want to travel from “u” to “z” then what will be the shortest path ??

u + x + y + z will cause only 3 , if you see all the other paths will be causing more cost.

But what if there  1000 nodes we cannot count it and find which is the best path available. So we have to come up with some algorithm to do this.

There are many algorithms doing the same :

• Dijkstra’s algorithm
• Bellman-ford algorithm
• Floyd Algorithm.

Dijkstra’s algorithm

One of the widely used single-source algorithm for finding the shortest path which is having non-negative edges. This will give you the shortest path from one point to any other point in the graph.

Each vertex will be having an distance attribute which is keeping track of the minimum  distance to that node from the source.

class Node{ private Integer name; private Integer distance;    }

Now we need keep TWO SETs

1) To keep track of all the vertices which has not processed

2) To keep track of all the vertices which has processed

But in reality we will be keeping all the Nodes in priority queue , So that we can get the Node with minimum distance in the queue. And each time we will be deleting the minimum Node because there won't be any case we get a better minimum for that Node. This can be easily understood if we would have sort the graph in its topological order.

Look at the above which has sorted the graph in topological order, where whatever node you take then all the node which is having indegree will be in the left and all the outdegree nodes will be  in the right. This proves that even if we delete the node from the priority queue it will be having the smallest distance at that point.  

• Firstly all the vertices will be stored in a priority queue
• And set the distance property of the Node to zero
• decrease key will be rearranging the priority queue such a way that min value comes in the head.

Time complexity

1. Building a min heap will take O(v) time ( see http://stackoverflow.com/questions/9755721/build-heap-complexity )
2. while loop will take O(v) since it has to iterate over all the vertices.
3. Getting the min value from the priority queue will costs you O(logV)
4. Iterating over all the edges will costs O(E)
5. Decrease key which is used to re arrange priority queue will take O(log V)

Total = O(V) + O(V) O(log V) + O(E) O(logV)

          O(V logV + E logV )

MIT lecture on Dijkstra   - https://www.youtube.com/watch?v=2E7MmKv0Y24 which covers the same in detailed. Algo starts from 27th minute.

Bellman - Ford algorithm

Dijkstra won't work if the graph is having negative weights and cycles where bellman ford comes for rescue with running time O(VE).

Floyd’s Algorithm

Until now we have talked about the single source shortest path, what if we want shortest path between each pair of vertices ?? Floyd’s algorithm comes to picture with running time of O(V^3).