以特定成本找到有向图中的所有路径 [英] Finding all paths in directed graph with specific cost

查看:179
本文介绍了以特定成本找到有向图中的所有路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

假设我们有定向的加权图。我们的任务是找到两个顶点(源和目的地)之间的所有路径,其成本小于或等于=< N.我们只访问每个顶点一次。在后面的版本中,我想添加一个条件,即源可以是目的地(我们只是做一个循环)。



我认为可以通过修改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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆