功能需要很长时间

Question

我目前正在尝试获取来自节点 1 的唯一路径的数量.. 加权有向无环图的最大长度 N，我已经计算出最大长度，但我一直坚持获取 NUMBER给定最大长度的路径...

数据是这样输入的：

91 120  # Number of nodes, number of edges

1 2 34

1 3 15

2 4 10

..... 作为节点1->节点2，权重为34，

I input my data using a diction so my dict looks like:
_distance = {}
_distance = {1: [(2, 34), (3, 15)], 2: [(4, 10)], 3: [(4, 17)], 4: [(5, 36), (6, 22)], 5: [(7, 8)],...ect

我已经弄清楚如何使用这个实现最长的路径长度：

首先我制作一个顶点列表

class Vertice:
    def __init__(self,name,weight=0,visted=False):
        self._n = name
        self._w = weight
        self._visited = visted
        self.pathTo

for i in range(numberOfNodes): # List of vertices (0-n-1)
  _V = Vertice(i) 
  _nodes.append(_V)

接下来我遍历我的字典，将每个节点设置为它可能的最大权重

        for vert, neighbors in _distance.iteritems():
        _vert = _nodes[vert-1] # Current vertice array starts at 0, so n-1


        for x,y in neighbors:  # neighbores,y = weight of neighbors
            _v = _nodes[x-1]   # Node #1 will be will be array[0]

            if _v._visited == True:
                if _v._w > _vert._w+y:
                    _v._w = _v._w
                else:
                    _v._w = y + _vert._w

            else:

                _v._w = y + _vert._w
                _v._visited = True

完成后，最后一个节点将具有最大权重，因此我可以调用

max = _nodes[-1]._w

获得最大重量。这似乎执行得很快，即使在更大的数据集上执行时也能轻松找到最大长度路径，然后我将我的最大值运行放入此函数中：

#  Start from first node in dictionary, distances is our dict{}
#  Target is the last node in the list of nodes, or the total number of nodes.
numLongestPaths(currentLocation=1,target=_numNodes,distances=_distance,maxlength=max)

def numLongestPaths(currentLocation,maxlength, target, sum=0, distances={}):


    _count = 0

    if currentLocation == target:
        if sum == maxlength:
                _count += 1

    else:
        for vert, weight in distances[currentLocation]:
            newSum = sum + weight
            currentLocation = vert
            _count += numLongestPaths(currentLocation,maxlength,target,newSum,distances)

    return _count

一旦我们到达结束节点，我就简单地检查一下我们当前的总和是否是最大值，如果是，则在我们的计数中加一，如果不是通过。

这适用于输入，例如 8 个节点，最长路径为 20，找到 3 条路径，以及输入，例如 100 个节点，最长长度为 149，并且只有 1 个该长度的唯一路径，但是当我尝试做一个有91个节点的数据集，例如最长路径1338，唯一路径数为32，该函数需要非常长的时间，它可以工作但是很慢。

有人能给我一些提示，告诉我我的函数有什么问题导致它花了这么长时间从 1..N 找到路径长度 X 的数量吗？我假设它得到指数运行时间但我不确定如何修复它

感谢您的帮助！

编辑：好吧，我想得太多了，以错误的方式解决了这个问题，我重组了我的方法，我的代码现在如下：

# BEGIN SEARCH.
    for vert, neighbors in _distance.iteritems():
        _vert = _nodes[vert-1] # Current vertice array starts at 0, so n-1


        for x,y in neighbors:  # neighbores

            _v = _nodes[x-1]   # Node #1 will be will be array[0]

            if _v._visited == True:
                if _v._w > _vert._w+y:
                    _v._w = _v._w
                elif _v._w == _vert._w+y:
                        _v.pathsTo += _vert.pathsTo
                else:
                    _v.pathsTo = _vert.pathsTo
                    _v._w = y + _vert._w

            else:

                _v._w = y + _vert._w
                _v.pathsTo = max(_vert.pathsTo, _v.pathsTo + 1)
                _v._visited = True

我向我的顶点 class 添加了一个 pathsTo 变量，它将保存最大长度的唯一路径的数量

Answer 1

你的 numLongestPaths 很慢，因为你递归地尝试每一条可能的路径，而且其中的路径可能呈指数级增长。找到一种方法来避免对任何节点多次计算 numLongestPaths。

另外，您原来的 _w 计算被破坏了，因为当它计算一个节点的 _w 值时，它没有做任何事情来确保它所依赖的其他 _w 值本身是正确的计算。您需要避免使用未初始化的值； topological sort 可能有用，尽管听起来顶点标签可能已经按拓扑排序顺序分配。

Answer 2

除了@user2357112的回答，这里还有两个额外的建议

语言

如果您希望此代码尽可能高效，我建议使用 C。Python 是一种很棒的脚本语言，但与编译的替代语言相比确实很慢

数据结构

节点以有序的方式命名，因此您可以通过使用列表而不是字典来优化您的代码。即

_distance = [[] for i in range(_length)]

功能需要很长时间

Function takes a long time

python

algorithm

directed-acyclic-graphs

longest-path

weighted-graph

语言

数据结构