Least cost path in given digraph from given source to destination having exactly m edges

Given a weighted digraph (Directed Graph), find the least cost path from given source to destination that have exactly m edges.


For example, consider below graph,

 
shortest-path


Let source = 0, destination = 3, no. of edges m = 4

It has 3 routes from source 0 to destination 3

0-1-5-2-3 having cost 17
0-1-6-5-3 having cost 19
0-6-5-2-3 having cost 8

The solution should return the least-cost route i.e. 8

 
Whenever we see the term shortest, the first thing we should think about is doing a BFS traversal. So here also we start BFS traversal from the given source vertex. Usually BFS don’t explore already discovered vertex again, but here we do the opposite. In order to cover all possible paths from source to destination, we remove this check from BFS. But what if the graph contains a cycle? Removing this check will cause program to go into an infinite loop. We can easily handle that if we don’t consider nodes having BFS depth of more than m.

In below solution, we maintain three things in BFS queue node –

  • current vertex number
  • current depth of BFS (i.e. how far is current node from source?) and
  • cost of current path choosen so far

So whenever we encounter any node whose cost of path is more and required BFS depth is reached, we update the result. The BFS will terminate when we have explored every path in the given graph or BFS depth exceeds m.

 
This is demonstrated below in C++:
 

Download   Run Code

Output:

8

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of