寻找特定代价下有向图中的所有路径

Question

假设我们有一个有向加权图。我们的任务是找到所有源点和目标点之间成本小于或等于N的路径。我们只访问每个顶点一次。在以后的版本中，我想添加一个条件，即源可以是目标（我们只需制作一个循环）。

我认为可以使用修改后的Dijkstra算法来实现，但我不知道如何实现这样的事情。谢谢任何帮助。

- kozooh

---

由于没有代码，我会将其标记为与语言无关。否则，准备因为缺乏努力或不是一个真正的问题而被踩。 - sehe

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

- jma127

---

非常感谢！算法工作得非常好，除了（在我看来）函数中长度 N 的条件应该放在第一位。否则，我们还会将到达目的地但其成本超过 N 的路径添加到列表中。 - kozooh

Answer 2

您想在有向图中找到从点A到点B的所有路径，例如从A到B的距离小于N，并允许A=B的可能性。

Dijkstra算法是专门用来在图中找到从一个点到另一个点的最短路径，并在此过程中放弃许多其他路径。因此，如果我们包括重叠路径，它不能用于查找所有路径。

您可以通过在图中进行广度优先搜索来实现目标，在其各自的堆栈中保留覆盖树的每个分支（如果节点非常连接，则会获得大量堆栈），并停止在深度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;

- didierc

---

如果您不需要重叠路径，则回溯答案是您所需的。 - didierc

Answer 3

我认为对于jma127建议的递归回溯算法，一个可能的改进（取决于问题的规模和最大成本N）是预先计算每个节点到目标的最小距离（最短路径树），然后将以下内容附加到测试条件中以终止您的递归：

• 当您到达一个节点时，其到目标的最小距离大于最大成本N减去到达当前节点的距离。

如果需要多次运行算法以处理不同的源和目标，则可以在开始时运行Johnson算法，以创建所有节点对之间最短路径的矩阵。

- Luca Citi