寻找与特定的成本向图的所有路径(Finding all paths in directed grap

假设我们有指示，加权图。我们的任务是找到beetween两个顶点（源和目的地），它的成本小于或等于= <N。我们访问每个顶点一次的路径。在以后的版本我想补充的是，源可以是目的地的条件（我们只是做一个循环）。

我认为它可以改进Dijkstra算法来完成，但我不知道如何实现这样的事情。谢谢你的帮助。

Answer 1:

你可以使用递归回溯来解决这个问题。终止您的递归时：

你到了目的地
您访问已访问过的节点
你的路径长度超过N.

伪代码：

list curpath := {}
int dest, maxlen
def findPaths (curNode, dist):
    if curNode = dest:
        print curpath
        return
    if curNode is marked:
        return
    if dist > maxlen:
        return
    add curNode to curpath
    mark curNode
    for nextNode, edgeDist adjacent to curNode:
        findPaths(nextNode, dist + edgeDist)
    remove last element of curpath

Answer 2:

要找到从A点到B点的有向图的所有路径，如距离从A到B是小于N时，并且允许的可能性，即A = B.

Dijkstra算法是taylored找到从一个点到另一个点在图中最小的路径，并丢弃许多其他所有一路走来，可以这么说。正因为如此，它不能被用来发现所有的路径，如果我们包括重叠路径。

您可以通过执行图中的广度优先搜索实现自己的目标，保持覆盖树的每个分支在其上堆栈（你会得到他们的大量节点是否很好的连接），并在深度N.停止这已经达到了B中的所有分支都放在一旁。一旦深度n所覆盖，你把它并未达到B.将剩余的所有路径，还有一个扔在一边放在一起成为您的解决方案。

您可以选择添加未在你的路径循环，在这种情况下你必须检查在搜索的每一步，如果新到达的节点已经是迄今为止覆盖的路径的限制和清理这条道路，如果它是案件。

下面是一些伪代码：

function find_paths(graph G, node A):
list<path> L, L';

L := empty list;
push path(A) in L;
for i = 2 to N begin
   L' := empty list;
   for each path P in L begin
       if last node of P = B then push P in L'
       else
       for each successor S of last node in P begin
           if S not in P then
              path P' := P;
              push S in P';
              push P' in L';
           endif
       end
       endif
   end
   L := L';
end

for each path P in L begin
  if last node of P != B
  then remove P from L
  endif
end
return L;