Проверяйте, только если два узла находятся на заданном расстоянии (длина пути) в графе

Question

Я пытаюсь реализовать функцию python, которая проверяет, находятся ли два заданных узла (start и goal) на определенном расстоянии (скажем, dist = 4) на графике.

Одним из грубых способов является поиск кратчайшего пути (используя Breadth First Algorithm) между двумя узлами, а затем проверить, меньше ли длина кратчайшего пути (или равна), чем заданное расстояние (dist = 4). Но это, очевидно, не лучшее решение и имеет много накладных расходов. Начиная с этих двух функций python, можете ли вы направить меня к тому, как я могу изменить эти функции, чтобы иметь такую ​​функцию?

Как я уже говорил, меня не интересует найденный путь как таковой. Весь наш интерес заключается в том, являются ли два узла в пределах предписанным расстоянием друг от друга. A YES или NO флаг возврата должен быть достаточным.

def bfs_paths(graph, start, goal): 
    queue = [(start, [start])] 
    while queue: 
     (vertex, path) = queue.pop(0) 
     for next in graph[vertex] - set(path): 
      if next == goal: 
       yield path + [next] 
      else: 
       queue.append((next, path + [next])) 

def shortest_path(graph, start, goal): 
    try: 
     return next(bfs_paths(graph, start, goal)) 
    except StopIteration: 
     return None 

Answer 1

Вам не нужно найти кратчайшее расстояние между ними. Все, что вам нужно сделать, это отключить ваши bfs после нужного dist. Если вы не заходите на узел цели до обрезания, тогда расстояние между стартом и целью больше dist. Также вы можете использовать dfs аналогичным образом. Отрезать поиск, когда глубина больше, чем dist. Этот метод поиска называется Depth Limited Search.