В настоящее время я работаю над попыткой получить количество уникальных путей от узла 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, функция занимает очень ДЛИННЕЕ, она работает, но очень медленно.

Может ли кто-нибудь дать мне несколько советов о том, что не так с моей функцией, из-за чего так долго нужно искать # путей длиной X от 1 до N? Я предполагаю, что у него экспоненциальное время работы, но я не уверен, как это исправить

Спасибо за помощь!

РЕДАКТИРОВАТЬ: Хорошо, я слишком много думал об этом и делал это неправильно, я реструктурировал свой подход, и теперь мой код выглядит следующим образом:

# 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

Я добавил переменную pathsTo в свой класс Vertice, и она будет содержать количество уникальных путей максимальной длины