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,

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include <iostream> #include <queue> #include <vector> #include <climits> using namespace std; // data structure to store graph edges struct Edge { int src, dest, weight; }; // class to represent a graph object class Graph { public: // construct a vector of vectors to represent adjacency list vector<vector<Edge>> adjList; // Graph Constructor Graph(const vector<Edge> &edges, int N) { // resize the vector to N elements of type vector<Edge> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) { adjList[edge.src].push_back(edge); } } }; // BFS Node struct Node { int vertex, depth, weight; }; // Perform BFS on graph g starting from vertex v int modifiedBFS(Graph const &g, int src, int dest, int m) { // create a queue used to do BFS queue<Node> q; // push source vertex into the queue q.push({src, 0, 0}); // stores least-cost from source to destination int minCost = INT_MAX; // run till queue is not empty while (!q.empty()) { // pop front node from queue Node node = q.front(); q.pop(); int v = node.vertex; int depth = node.depth; int cost = node.weight; // if destination is reached and BFS depth is equal to m // update minimum cost calculated so far if (v == dest && depth == m) minCost = min(minCost, cost); // don't consider nodes having BFS depth more than m. // This check will result in optimized code and also // handle cycles in the graph (else loop will never break) if (depth > m) break; // do for every adjacent edge of v for (Edge edge : g.adjList[v]) { // push every vertex (discovered or undiscovered) into // the queue with depth as +1 of parent and cost equal // to cost of parent plus weight of current edge q.push( {edge.dest, depth + 1, cost + edge.weight} ); } } // return least-cost return minCost; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 6, -1}, {0, 1, 5}, {1, 6, 3}, {1, 5, 5}, {1, 2, 7}, {2, 3, 8}, {3, 4, 10}, {5, 2, -1}, {5, 3, 9}, {5, 4, 1}, {6, 5, 2}, {7, 6, 9}, {7, 1, 6} }; // Number of vertices in the graph int N = 8; // create a graph from edges Graph g(edges, N); int src = 0, dest = 3, m = 4; // Do modified BFS traversal from source vertex src cout << modifiedBFS(g, src, dest, m); return 0; } |

`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