Dear reader, welcome to the article on the problem named "Shortest Path in Weights" . The algorithm, which we are going to learn today, is known as Dijkstra's
Trust me, the algorithm itself is easier than the pronunciation. The algorithm is very intuitive, as it follows a Greedy Approach. The algorithm is also known as "Single Source Shortest Paths Algorithm".
So, enough talk, let's jump into the problem!
- You are given an undirected graph and a source vertex. The vertices represent cities and the edges represent distance in kms.
- The graph is weighted in nature. The weights of all edges are non-negative.
- You are required to find the shortest path to each city (in terms of kms) from the source city along with the total distance on the path from source to destinations.
Note: Input is given in the form of adjacency list. Please go through the output format once, before learning the algorithm.
Please note that this problem is different from Single Source Source Shortest Path in terms of count of edges (in unweighted graph).
For the shortest path in terms of edge count, we had used BFS traversal in the previous problem "Spread of Infection" .
Here, we need to find the shortest path in terms of weight. The shortest path may (or may not) be longer in terms of edge count.
In the above example, the shortest weighted path from 0 to 1 is equal to 10 via "02341", which is longer from the path "01".
You will be amazed to read that, we just need a slight modification to our BFS algorithm, so that it can find the shortest path in terms of weight.
Can you guess where we need to tweak?
In BFS traversal, we used a queue data structure. But since we can only maintain FIFO order in the queue, we cannot get the shortest path in terms of weight.
For Dijkstra's algorithm, we just need to replace the queue with a priority queue, and that's it.
You should be able to analyze that the Priority Queue pops out the element with higher priority among all the candidates.
We should have a path with the shortest distance as the highest priority. Hence, we will declare a Pair class, which will have a weight so far, storing the maximum distance of that node from source vertex.
But, how will our priority queue be able to decide which Pair object has higher priority?
So, our Pair class must implement a comparable interface. Please refer to the "Comparable vs Comparator" video of "Priority Queue" if you do not know how to define a custom comparator for user defined classes. We will define the compareTo function which compares the values of weight so far (wsf).
- Make a boolean array visited of size n (number of vertices), which will store whether the node is visited or not. Initially all values will be false (no node is visited).
- Initialize an empty priority queue pq which stores objects of type Pair, which have three data members: v (node's value), psf (path so far), and wsf (weight so far).
- Insert a Pair(src, src + "", 0) into the priority queue. It means that we are starting the algorithm with source vertex src, and weight so far as 0.
- Run the algorithm until there are some nodes present in the priority queue, i.e. until pq.size() > 0.
- Pop the top element of the priority queue and store it in a Pair object rem.
- If the top element is already visited (we reached the current node from a shorter path before), then simply continue.
- Else, mark the top element as visited, i.e. visited[rem.v] = true.
- Print the node's value along with the path so far and the shortest distance using the statement: System.out.println(rem.v + " via " + rem.psf + " @ " + rem.wsf);
- Traverse through all the neighbours of the current vertex.
- If the neighbour vertex is not visited (visited[e.nbr] == false), then add the node in the priority queue by adding the node's value in path so far and distance in weight so far.
Note: Before reading the Code, we recommend that you must try to come up with the solution on your own. Now, hoping that you have tried by yourself, here is the Java code.