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

假设我们有无向图，加权图。 我们的任务是找到两个顶点（源和目标）之间的所有路径，其总成本等于= N。我认为可以用修改后的Dijkstra算法与BFS或DFS结合来完成，但我不知道如何实现这样的事情。 谢谢你的帮助。

---

假设您有一个框架/库来创建图形数据结构并对其进行遍历，如果您跨越资源约束，则可以使用早期返回来进行回溯深度优先搜索。 在伪代码中：

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));      
}

然后你可以把它叫做DFS(start, goal, List<Vertex>(empty), N)

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

上一篇: Finding paths in undirected graph with specific cost

下一篇: Shortest path algorithm with both vertex and edge costs