Finding paths in an undirected graph with a certain cost

Question

Suppose we have an undirected weighted graph. Our task is to find all the paths between two peaks (source and destination), the total cost of which is N. I think that this can be done using the modified Dijkstra algorithm in combination with BFS or DFS, but I have no idea how to implement this Thing. Thanks for any help.

Answer 1

Assuming you have a framework / library for creating a graph data structure and for moving it, you can do a depth search with search depth with an early return if you cross the resource limit. In pseudo code:

void DFS(Vertex current, Vertex goal, List<Vertex> path, int money_left) { // oops if (money_left < 0) return; // avoid cycles if (contains(path, current) return; // got it! if (current == goal)) { if (money_left == 0) print(path); return; } // keep looking children = successors(current); // optionally sorted from low to high cost for(child: children) DFS(child, add_path(path, child), money_left - cost(child)); } 

and you can call it DFS(start, goal, List<Vertex>(empty), N)