Поиск всех путей в взвешенном графе от узла A до B с весом K или ниже

Question

У меня есть ориентированный граф с источником и целью. вес каждого ребра равен 1. Узлы не имеют веса. Мне нужно найти эффективный способ (я пишу на C #, но я не думаю, что это уместно), чтобы найти ВСЕ пути от источника к цели, это вес пути (или количество ребер, которое являетсято же самое с этими деталями) будет меньше или равно определенному значению, давайте назовем его K.

Я подумал, что возможно запустить Dijkstra для каждого значения от 1 до K, но так как K может быть очень большимэто не будет эффективным. Я искал некоторые ответы, но также был очень похожий на мой вопрос, я не нашел этот ответ так услужливо.

( Найти весь простой путь от узла A к узлу B в прямом взвешенном графике с суммой весов за вычетом определенного значения? )

Answer 1

Вы можете просто запустить DFS от источника до цели, чтобы проанализировать все пути. Если вам нужно найти количество путей, вы останавливаетесь, когда достигаете глубины K, возвращающей 0, и когда вы достигаете цели, возвращающей 1, и если вам нужно также описать пути, вы можете построить дерево во время исследования с помощью DFS. Сложность будет O (E), где E - число ребер

Здесь смесь питона и псевдокода:

def DFS(node, depth, target, visited, graph, max_depth):
  visited.add(node)
  if depth >= max_depth:
    return Null
  elif node == target:
    return new_tree_node(node)
  else:
    sub_trees = list()
    for connected_node in graph[node]:
      if connected_node not in visited:
        sub_tree = DFS(connected_node, depth+1, target, visited, graph, max_depth)
        if sub_tree != Null:
          sub_trees.append(sub_tree)

    if length(sub_trees) > 0:
      tree_node = new_tree_node(node)
      for sub_tree in sub_trees:
         tree_node.add_child(sub_tree)
      return tree_node
    else:
      return Null

tree = DFS(source, 0, target, set(), graph, K)

PS: это решение можно легко адаптировать к взвешенному графу какхорошо