假设我们有一个有向加权图。我们的任务是找到所有源点和目标点之间成本小于或等于N的路径。我们只访问每个顶点一次。在以后的版本中,我想添加一个条件,即源可以是目标(我们只需制作一个循环)。
我认为可以使用修改后的Dijkstra算法来实现,但我不知道如何实现这样的事情。谢谢任何帮助。
我认为可以使用修改后的Dijkstra算法来实现,但我不知道如何实现这样的事情。谢谢任何帮助。
您可以使用递归回溯来解决这个问题。当发生以下情况时,请终止递归:
伪代码:
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
您想在有向图中找到从点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;
我认为对于jma127建议的递归回溯算法,一个可能的改进(取决于问题的规模和最大成本N)是预先计算每个节点到目标的最小距离(最短路径树),然后将以下内容附加到测试条件中以终止您的递归:
如果需要多次运行算法以处理不同的源和目标,则可以在开始时运行Johnson算法,以创建所有节点对之间最短路径的矩阵。