Как найти кратчайший маршрут в графе с дополнительными требованиями к маршруту?

Question

[keddad]

У меня есть граф, на каждом ребре - некоторый положительный вес. Для поиска кратчайшего маршрута между двумя точками я использую алгоритм Дейкстры. У меня появляется дополнительное условие: система заправок. Т.е. в некоторых из вершин есть "заправки", которые восполняют наш запас хода, и без заправок я могу передвинуться только на некоторое n (n - сумма пройденных от заправки весов ребер). Как в таком случае мне следует минимизировать кол-во заправок на маршруте? Если мы находимся в ноде с заправкой, мы не обязательно должны ее использовать.

Comments

[Wataru]

Граф большой? Насколько длинные ребра и большой бак можно заправлять (насколько большое n)?

[Антон Федорян]

был такой вопрос не так давно на SO

[keddad]

wataru, До 10000 нод с 10000 ребрами, при n до 500

Answer 1

[xmoonlight]

Сначала ищем все возможные пути с заправками: ([текущая заправка:на какое расстояние заправляет] + [текущий запас топлива: на какое макс.расстояние можно проехать без заправки] - [сумма рёбер пути от текущего узла до следующей заправки или пункта назначения] ) > 0.
Выбираем все возможные варианты, чтобы всегда было топливо в баке.

Потом, уже только из них, ищем минимальное кол-во заправок на кратчайшем пути.

Answer 2

[Wataru]

При данных ограничениях можно создать искусственный граф, где каждая вершина соответствует вершине в исходном графе и некоторому запасу топлива (я обозначу такую вершину как (v, f) - в вершине v с топливом f).
Вершин в таком графе будет до 500*10000. Для каждого ребра v->u длинной l в исходном графе создаем ребро из вершины (v, f) в вершину (u, f-l) для всех f (т.е. из вершины v, имея f топлива, можно попасть в вершину u, имея f-l топлива). Эти ребра ценой 0. Также, в каждую вершину v, где есть заправка, добавьте ребро (v, f) -> (v, n) ценой 1 (заправились до упора). В графе будет до 500*10000 + 500*10000 ребер.

Теперь запустите там обход в ширину с двумя очередями или deque из вершины (start, n) пока не найдете путь в любую вершину (finish, f). Длина пути будет равна количеству заправок. Преходы по ребрам ценой 1 - это процесс заправки, по ребрам цены 0 - просто передвижения в исходном графе.

Это известное обобщение обхода в ширину на 0-1 графе:
Когда берете вершину из deque и смотрите всех ее соседей, если длина ребра до соседа 1, то кладете конец ребра в конец deque, а если цена 0 - то в начало. С двумя очередями делается так: пока очереди не пусты, берем вершину из текущей очереди и кладем ее соседей на расстоянии 0 в конец той же очереди, а соседей через ребро длины 1 - во вторую очередь. Когда текущая очередь опустеет, переходим к другой и так далее.

Comments

[Mercury13]

500·10k — что-то до хрѣна.

[keddad]

Mercury13, Да нет, немного, тем более, это худший случай

[keddad]

Я не вполне понимаю логику построения искусственного графа. Как мы должны вычислить это f для вершин, в которых нет заправки? Рассчитать кратчайший маршрут от ближайшей заправки?

[Wataru]

Mercury13, вообще не много, учитывая что алгоритм работает за линию от количества вершин+ребер в этом новом графе.

keddad, Логика построения - рассматриваем все возможные варианты. Вот вы можете как-то покататься и оказаться в вершине 42 с 1 "литра" топлива. А можете как-то по другому покататься и приехать туда с 100 литров топлива. Вот это 2 разные вершины в новом графе. Они все различные от 0 до n. У вас все состояние описывается двумя величинами: где вы и сколько у вас топлива сейчас топлива. Мы все это пространство состояний описываем с помощью этого искусственного графа. Ведь совершенно неважно, как вы раньше ездили, ведь если вы в вершине 42 с 10 литрами топлива, то вы дальше можете делать все то же самое. Поэтому и получается n * "количество вершин" вершин в новом графе. Далее мы в этом пространстве состояний ищем минимальный путь.

Answer 3

[Mercury13]

ВАРИАНТ 1. Расстояние приоритетнее кол-ва заправок.

Моё решение — в каждой вершине хранить не просто цифру пройденного расстояния, а список: «расстояние/запас топлива/предыдущая вершина». И расстояние, и топливо не убывают.

С этими списками можно делать такие операции:

1. Добавить расстояние + израсходовать топливо. Для каждого элемента списка расстояние′ = расстояние + x, топливо′ = топливо − y. Если получается нехватка топлива — что ж, не повезло, этого элемента в списке не будет.
2. Добавить расстояние + израсходовать топливо + заправиться. Аналогично, но оставляем один элемент — соответствующий наименьшему расстоянию, где хватает топлива. расстояние′ = расстояние + x, топливо′ = полный бак.
3. Добавить очередной элемент в список. Тогда удаляем из списка те элементы, где расстояние не меньше, а запас топлива не больше.

После этого на оптимальном маршруте проводим оптимизацию заправок.

Если граф такой, что бывает много «ничьих» по расстоянию, приходится эти ничьи разруливать.
1. Если есть несколько равноценных маршрутов — храним их ВСЕ.
2. Например, можно заполучить все такие маршруты, и на каждом провести оптимизацию заправок.

Можно также вместо расстояния хранить список «расстояние, кол-во заправок» с лексикографическим порядком на ней и другой операцией «прибавить+заправиться».

ВАРИАНТ 2. Кол-во заправок приоритетнее расстояния.

Аналогично первому, только роль расстояния играет пара «кол-во заправок, расстояние» с лексикографическим порядком на ней.