Как найти кратчайший путь, удовлетворяющий ограничениям на графике

#python #graph #graph-theory

#python #График #теория графов

Вопрос:

Я пытаюсь найти кратчайший путь на взвешенном графике, учитывая ограничение, что путь должен иметь общее расстояние меньше некоторого параметра (скажем, 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

Другое дело, что я не хочу сравнивать на основе расстояния пути, начинающегося с данного узла, но на основе расстояния ВСЕГО ПУТИ от исходной начальной точки. Хотя я не знаю лучшего способа сделать это здесь.

1. Вы имеете в виду кратчайший с точки зрения количества переходов или расстояния (последнее тривиально, поэтому я предполагаю, что это первое)?

2. Вы пытаетесь найти путь, содержащий наименьшее количество ребер, где общая стоимость пути (сумма весов его ребер) меньше 1000?

Ответ №1:

Я действительно не могу разобраться в предоставленном вами коде ( firststep_distance ? firststep_outer_distance ?). Не могли бы вы указать название алгоритма, который вы пытаетесь реализовать?

Если вы просто что-то придумываете на лету, и вы не ставите перед собой цель заново изобрести теорию графов для образовательных целей, я бы посоветовал поискать стандартный алгоритм кратчайшего пути. Если вы можете гарантировать, что ваши веса неотрицательны, то стандартом является алгоритм Дейкстры. Википедия сообщит об улучшенной асимптотической среде выполнения, если вы подкрепите ее кучей Фибоначчи, но не попадайтесь в эту ловушку — по-видимому, кучи Фибоначчи имеют ужасную производительность на практике.

Если Дейкстры недостаточно, взгляните на A*-search методы. Здесь, как и во всех вопросах алгоритма, CLR — ваш лучший гид, но Википедия чертовски близко. Надеюсь, это поможет!

Ответ №2:

Я также не могу точно сказать, что происходит, без дополнительного кода или информации, но это касается:

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

Если вы уменьшаете maxTotalDistance при каждом рекурсивном вызове, то firststep_distance (который, я полагаю, является весом пути) должен быть больше оставшегося расстояния, а не меньше.