CODEWITHSUNDEEP
graphcomplexity-theorydijkstradepth-first-searchbacktracking
IlanMosheShimsoni
IlanMosheShimsoni

Reputation: 41

Finding paths in undirected graph with specific cost

Suppose we have undirected, weighted graph. Our task is to find all paths beetween two vertices (source and destination) which total cost equal = N. I think it can be done with modified Dijkstra's algorithm combined with BFS or DFS, but I have no idea how implement such thing. Thanks for any help.

Upvotes: 4

Views: 525

Answers (1)

TemplateRex
TemplateRex

Reputation: 70516

Assuming you have a framework / library to create a graph data structure and to traverse it, you could do a backtracking depth-first search with an early return if you cross your resource constraint. 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 then call it as DFS(start, goal, List<Vertex>(empty), N)

Upvotes: 3

Related Questions