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.

---

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)

链接地址: http://www.djcxy.com/p/35254.html

上一篇: 线性时间单一

下一篇: 在具有特定成本的无向图中查找路径