graph - 在有向图中以特定成本查找所有路径

Question

假设我们有有向加权图。我们的任务是找到成本小于或等于 =< 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 的算法被定制为在图中找到从一个点到另一个点的最小路径，并在此过程中丢弃许多其他点，可以这么说。因此，如果我们包含重叠的路径，它不能用于查找所有路径。

您可以通过在图中进行广度优先搜索来实现您的目标，将覆盖树的每个分支保持在其堆栈中（如果节点连接得很好，您将获得大量分支），然后在深度 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;

Answer 3

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

• 您到达一个节点，其与目的地的最小距离大于最大成本 N 减去到达当前节点所经过的距离。

如果需要针对不同的源和目的地多次运行该算法，则可以在开始时运行例如约翰逊算法，以创建所有节点对之间的最短路径矩阵。