Given a weighted graph, find the maximum cost path from given source to destination that is greater than a given integer x. The path should not contain any cycles.

For example, consider below graph,

Let *source = 0, k = 40*

The maximum cost route from source vertex 0 is `0-6-7-1-2-5-3-4` having *cost 51* which is more than k. The solution should return 51.

The idea is to do a breadth-first search traversal. BFS is generally used to find shortest paths in graphs/matrix but we can modify normal BFS to meet our requirements. By modifying BFS, we don’t mean using priority queue that picks up the maximum weighted edge at every step as that approach will definitely fail. A low-weight edge can also be involved in maximum cost path as there might be higher weight edges connected through it.

#### So how can we use BFS?

Usually BFS don’t explore already discovered vertex again, but here we do the opposite. In order to cover all possible paths from given source, we remove this check from BFS. But if the graph contains a cycle, removing this check will cause program to go into an infinite loop. We can easily handle that if maintain list of nodes visited so far in current path for a node a queue. Basically we maintain three things in BFS queue node –

- current vertex number
- cost of current path chosen so far
- set of nodes visited so far in current path

So whenever we encounter any node whose cost of path is more, we update the result. The BFS will terminate when we have explored every path that doesn’t result into a cycle.

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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#include <iostream> #include <queue> #include <vector> #include <set> #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 of Edge to represent an adjacency list vector<vector<Edge>> adjList; // Constructor Graph(vector<Edge> const &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) { int src = edge.src; int dest = edge.dest; int weight = edge.weight; adjList[src].push_back({src, dest, weight}); adjList[dest].push_back({dest, src, weight}); } } }; // BFS Node struct Node { // current vertex number and cost of current path int vertex, weight; // set of nodes visited so far in current path set<int> s; }; // Perform BFS on graph g starting from vertex v int modifiedBFS(Graph const &g, int src, int k) { // create a queue used to do BFS queue<Node> q; // add source vertex to set and push it into the queue set<int> vertices; vertices.insert(0); q.push({src, 0, vertices}); // stores maximum-cost of path from source int maxCost = INT_MIN; // 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 cost = node.weight; vertices = node.s; // if destination is reached and BFS depth is equal to m // update minimum cost calculated so far if (cost > k) maxCost = max(maxCost, cost); // do for every adjacent edge of v for (Edge edge : g.adjList[v]) { // check for cycle if (vertices.find(edge.dest) == vertices.end()) { // add current node into the path set<int> s = vertices; s.insert(edge.dest); // push every vertex (discovered or undiscovered) into // the queue with cost equal to (cost of parent + weight // of current edge) q.push( {edge.dest, cost + edge.weight, s} ); } } } // return max-cost return maxCost; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 6, 11}, {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 nodes in the graph int N = 9; // create a graph from edges Graph g(edges, N); int src = 0; int cost = 50; // Do modified BFS traversal from source vertex src int maxCost = modifiedBFS(g, src, cost); if (maxCost != INT_MIN) cout << maxCost; else cout << "All paths from source have their costs < " << cost; return 0; } |

`Output:`

51

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Nice one

This is a classical NP-hard problem.

So, is the solution, like, exponential time, or does it solve P = NP?