Самый короткий путь с максимальным числом вершин

Question

Я хочу найти кратчайший путь между двумя вершинами с дополнительным ограничением: max n можно посетить вершины. График направлен, связан, не отрицателен и может содержать циклы.

Пример:

1. Кратчайший путь 0-> 2 с п = 2 является
2. Кратчайший путь 0-> 3 с п = -
3. Кратчайший путь 0-> 3 с п = 4 является

До сих пор я реализовал Djikstras алгоритм, чтобы получить простой короткий путь, и моя идея состояла в том, чтобы сохранить счетчик из текущих посещенных вершин, если он превышает n, он принимает один или несколько шагов назад и пытается с другим путем .. но насколько я знаю, Djikstras не может использоваться для обратного отслеживания, как объяснено here.

Другая идея - как-то хранить каждый путь между каждым узлом в таблице. Но я не совсем уверен, как Джикстра может найти путь 0-> 2 с весом 18, так как это не самый короткий путь ...

Есть ли у кого-нибудь идеи, как решить эту проблему?

Answer 1

Разделенный каждую вершину в n вершин, то есть, для вершин u, мы создаем n вершины выражается как (u, 1) ... (u, n), второй номер показывает количество шагов в эту вершину. Для каждого ребра от u до v мы создаем ребро из (u, i) в (v, i + 1), где 1<=i<=n-1 в новом графике. Теперь, если вы хотите рассчитать кратчайший путь между u и v с n, просто сделайте Dijkstra из (u, 1), тогда ваш ответ min(result (v, i) | 1<=i<=n)

Общее количество вершин может быть n * n, поэтому сложность about O(n^2*log(n^2))

Answer 2

Возможно, попробуйте bfs и проверьте количество вершин на макс. Сохраните лучшие из тех, которые соответствуют ограничениям.

Heres об этом видео https://youtu.be/TvHV3PB8ANs

Nist.gov имеет некоторые Algos, а также.

Answer 3

Пусть COST_TO (v, n) - общий вес минимального пути к вершине v с n ребрами или меньше.

При п = 0, то ответ прост:

для всех V, COST_T (v, 0) = 0, если v является источником вершин и бесконечность в противном случае

При п> 0, COST_TO (v, n) - минимум COST_TO (v, n-1) и все COST_TO (w, n-1) + WEIGHT (w, v), где есть ребро от w до v

, поэтому для n = от 0 до N, отслеживать все вершины с бесконечной стоимостью COST_ (v, n) < вместе с их расходами и вычислять затраты для n из значений для n-1.

В то же время вы можете отслеживать минимальный путь веса к каждому v - каждый раз, когда вы обновляете стоимость v с помощью правила края, новый путь к v - это путь к w плюс этот край. Для этого удобен список с обратной связью.

Answer 4

Предположим, что вы хотите найти кратчайший путь от исходной вершины S до конечной вершины T, состоящей не более чем из K ребер. Я выбрал K, потому что n в вашем вопросе вводит в заблуждение - если вы хотите найти самый короткий путь, посещающий самое большее n вершины, где n - общее количество вершин, вы можете просто запустить Dijkstra, потому что любой простой путь имеет самое большее n вершины - я предполагаю, что это не то, что вы хотите здесь.

Затем, если вы хотите простую реализацию, Bellman-Ford хороший выбор здесь:

После i-th итерации внешнего цикла, алгоритм вычислил самый короткий путь от исходной вершины S в любую другую вершину, состоящий от at most i edges, поэтому он состоит из at most i + 1 vertices. Поэтому, чтобы решить вашу проблему, запустите K - 1 внешние петли Bellman-Ford и проверьте, правильно ли определено расстояние до конечной вершины T (отличается от бесконечности), и если да, то у вас есть результат. В противном случае T не может быть достигнут от S при посещении K или менее вершин.