Ограничение «ровно N ребер» значительно облегчает решение этой проблемы, чем если бы этого ограничения не существовало. По сути, вы можете решить N = 0 (только начальный узел), использовать его для решения N = 1 (все соседи начального узла), затем N = 2 (соседи решения с N = 1, выбирая путь с наименьшей стоимостью для узлов, которые связаны с несколькими узлами) и т. д.
В псевдокоде (используя {field: val} для обозначения «записи с полем с именем field со значением val»):
# returns a map from node to cost, where each key represents
# a node reachable from start_node in exactly n steps, and the
# associated value is the total cost of the cheapest path to
# that node
cheapest_path(n, start_node):
i = 0
horizon = new map()
horizon[start_node] = {cost: 0, path: []}
while i <= n:
next_horizon = new map()
for node, entry in key_value_pairs(horizon):
for neighbor in neighbors(node):
this_neighbor_cost = entry.cost + edge_weight(node, neighbor, i)
this_neighbor_path = entry.path + [neighbor]
if next_horizon[neighbor] does not exist or this_neighbor_cost < next_horizon[neighbor].cost:
next_horizon[neighbor] = {cost: this_neighbor_cost, path: this_neighbor_path}
i = i + 1
horizon = next_horizon
return horizon
Мы учитываем динамические веса, используя edge_weight(node, neighbor, i), что означает «стоимость перехода от node до neighbor на шаге времени i.
Это вырожденная версия алгоритма кратчайшего пути из одного источника, такого как алгоритм Дейкстры, но он намного проще, потому что мы знаем, что должны пройти ровно N шагов, поэтому нам не нужно беспокоиться о застревании в циклах с отрицательным весом или более длинные пути с более дешевыми весами, или что-нибудь в этом роде.