我目前正在尝试获取来自节点 1 的唯一路径的数量 .. 加权有向无环图的最大长度 N，我已经计算出获得最大长度，但我一直坚持获取给定路径的数量最长长度...
数据输入如下：
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
我在我的 Vertice 类中添加了一个 pathsTo 变量，它将保存 MAX 长度的唯一路径的数量