如何在图上找到满足约束条件的最短路径

我试图在给定约束路径必须总距离小于某个参数（比方说1000）的加权图上找到最短路径。如何在图上找到满足约束条件的最短路径

我试过以下，但我不知道为什么我的代码是错误的。

def directedDFS(digraph, start, end, maxTotalDist): 
    visited = [] 
    if not (digraph.hasNode(start) and digraph.hasNode(end)): 
     raise ValueError('Start or end not in graph.') 
    path = [str(start)] 
    if start == end: 
     return path 
    shortest = None 
    for node in digraph.childrenOf(start): 
     if (str(node) not in visited): 
      visited = visited + [str(node)] 
      firststep_distance = digraph.childrenOf(start)[node][0] 
      firststep_outer_distance = digraph.childrenOf(start)[node][1] 
      if (firststep_distance <= maxTotalDist): 
       newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance) 
       if newPath == None: 
        continue 
       if (shortest == None or TotalDistance(digraph,newPath) < TotalDistance(digraph,shortest)): 
        shortest = newPath 
    if shortest != None: 
     path = path + shortest 
    else: 
     path = None 
    return path

另一件事是，我不希望比较基于从给定节点开始的路径的距离，而是基于整个路径从原来的起点的距离。我不知道在这里做这件事的最好方法。

来源

2011-05-06 Glassjawed

你的意思是跳数或距离最短（后者是微不足道的，所以我猜这是前者）？ – NPE 2011-05-06 16:12:07

您是否试图找到包含总路径成本（其边缘权重之和）小于1000的最少边的路径？ – 2011-05-07 03:15:06

我真的不能让你提供的代码正面或反面（firststep_distance？firststep_outer_distance？）。你能提供你试图实现的算法的名字吗？

如果你只是在做一些事情，而你没有为了教育目的重新创建图论，我会建议查找一个标准的最短路径算法。如果你能保证你的权重是非负的，那么这个标准就是Dijkstra的算法。如果您使用斐波那契堆进行备份，维基百科会报告一个改进的渐近运行时间，但不会陷入该陷阱 - 显然，斐波那契堆在实践中表现糟糕。

如果Dijkstra's不够好，请查看A*-search方法。在这里，和所有的算法问题一样，CLR是你最好的指导，但维基百科是非常接近的。希望有所帮助！

来源

2011-05-06 16:04:35 Wang

我也真的不能告诉发生了什么事情没有更多的代码或信息，但这是关于：

 if (firststep_distance <= maxTotalDist): 
      newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance)

如果您在每次递归调用降低maxTotalDistance，然后firststep_distance（我假设是路径的重量）必须大于剩余距离，不能小于。

来源

2011-05-06 16:08:49 dfb

不，firststep_distance是路径中第一步的权重。我应该澄清一点。 – Glassjawed 2011-05-06 16:27:11

我错过了，按照路径的重量，我的意思是从开始到结点的边的权重。 – dfb 2011-05-06 16:34:20

如何在图上找到满足约束条件的最短路径

回答

相关问题