How To 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++:
 

Output:

8

Comments

Popular posts from this blog

How to change this to <%Html.ActionLink%> in my asp.net mvc application ?