以特定成本找到有向图中的所有路径 [英] Finding all paths in directed graph with specific cost
本文介绍了以特定成本找到有向图中的所有路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我认为可以通过修改Dijkstra算法,但我不知道如何实现这样的事情。感谢您的帮助。
解决方案
您可以使用递归回溯来解决此问题。在以下情况下终止递归:
- 您到达目的地
- 您访问已经存在的节点访问
- 您的路径长度超过N。
伪代码:
list curpath:= {}
int dest,maxlen
def findPaths(curNode,dist):
如果curNode = dest:
打印curpath
返回
如果curNode被标记:
返回
如果dist> maxlen:
返回
将curNode添加到curpath
标记curNode
用于nextNode,edgeDist与curNode相邻:
findPaths(nextNode,dist + edgeDist)
删除curpath的最后一个元素
Suppose we have the directed, weighted graph. Our task is to find all paths beetween two vertices (source and destination) which cost is less or equal =< N. We visit every vertex only once. In later version I'd like to add a condition that the source can be the destination (we just make a loop).
I think it can be done with modified Dijkstra's algorithm, but I have no idea how implement such thing. Thanks for any help.
解决方案
You could use recursive backtracking to solve this problem. Terminate your recursion when:
- You get to the destination
- You visit a node that was already visited
- Your path length exceeds N.
Pseudocode:
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
这篇关于以特定成本找到有向图中的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文