Modified Dijkstra's Algorithm to find shortest path by product of edge weights in Java

By Parthvi Mayurkumar Patel

This Java program can find a path from the source vertex to all the other vertices of a directed acyclic weighted graph such that the product of edge weights is minimum.

Dijkstra's Algorithm calculates the shortest path(sum of edge weights should be minimum) from a single source to all the other vertices of a directed acyclic weighted graph. It is based on the principle of relaxation where the distance (or cost) between 2 nodes is replaced by a smaller value until the shortest distance (or cheapest cost) is found.

How Dijkstra's Algorithm works:-

Firstly, Dijkstra’s algorithm begins with the source node, and it examines the entire graph to find the nearest node.

The nearest unvisited node is enqueued in the priority queue. It maintains a track of the currently examined shortest distance from each node in the priority queue to the source node and replaces these values if a shorter path is found.

Once the shortest path from the source node to another node has been found, the node is marked as “finalised” and is removed from the priority queue.

This process is being repeated until all the nodes in the graph have been marked "finalised", and the shortest path from the source node to all the other nodes has been found.

Modified Dijkstra's Algorithm:-

Dijkstra's Algorithm works on finding the minimum sum of edge weights. In order to find the shortest path by product of edge weights, we modify the algorithm to minimise the sum of logarithms of the edge weights.

Example- Let the edge weights be e1,e2,e3......en. We need to minimize their product i.e. e1*e2*e3*....*en.

log(e1*e2*e3*....*en)= log(e1) + log(e2) + log(e3) +.....+ log(en)

Since log is a monotonic function, we can use Djikstra's Algorithm for logarithm of weights to find their minimised product.

 

Problem used for the Sample Output-

Output:-