Кратчайший путь в графике, когда обязательно перепрыгивать через каждое второе ребро

Question

Я готовился к соревнованию по программированию и наткнулся на эту проблему, в которой я должен найти кратчайший путь от источника к месту назначения в взвешенном и ненаправленном графике, но мне нужно пропустить каждое второе ребро (поэтому его весне важный).Вес в графе - это положительные целые числа.

Исходное утверждение:

Клара и Джейк в поездке.Они едут по очереди, а водителя машины меняют после каждого города.Найдите кратчайший путь от источника до места назначения, чтобы Клара проехала наименьшее количество миль.Напишите, кто должен быть водителем автомобиля первым.

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

Редактировать: у пересеченных ребер вес равен 0, если ребро можно пропустить или нет, я должен проверить оба варианта.

Answer 1

Если я правильно понял, вы хотите найти кратчайший путь во взвешенном графе с дополнительной сложностью, состоящей в том, что вес пути является суммой веса нечетных ребер (1, 3, ...) или четные ребра (2, 4, ...) вдоль пути.

Вы можете сделать это, сначала создав новый граф:

1. для каждой вершины v в исходном графе, создайте две вершины в новом графе, одна будет называться even v, а другая odd v
2. , если (u, v) является ребром веса w в исходномдобавьте следующие грани к новому графику: (even u, odd v) с весом w и (odd u, even v) с весом 0

Затем выполните два обычных Дейкстры, чтобы найти кратчайший путь, достигающий odd destination и even destination от even source.Наименьший вес - самый короткий путь, если Клара едет первой.

Выполните ту же процедуру, начиная с odd source, чтобы найти кратчайший путь, если Клара едет второй.

Доказательство

Инвариант, который мы хотим иметь в новом графе:

• even v - вершина, достигнутая через путь, последний край которого даже пронумерован
• odd v - вершина, достигнутая по пути, последний край которого имеет нечетный номер

Поскольку мы только добавляем ребра от even до odd и от odd доeven этот инвариант верен для всего нового графа.Мы используем вес 0 для четных ребер, чтобы приспособить специальную весовую функцию для путей.

source в исходном графе соответствует even source в новом графе, если он достигнутпуть, содержащий 0 ребра, если Клара едет первым.Когда Клара едет второй, source отображается на odd source.

destination в исходном графике может отображаться либо на even destination, либо на odd destination в зависимости от количества ребер на пути.Выбрав кратчайший взвешенный путь к любому из них, мы обязательно найдем кратчайший путь, используя специальную весовую функцию в исходном графике.

Answer 2

Модифицируйте Bellman-Ford, чтобы отслеживать два расстояния для каждой вершины: минимальное расстояние, достижимое через четное и нечетное число ребер.На этапе обновления (шаг 2 в статье из Википедии) обновите расстояния с нулевым или фактическим весом в зависимости от длины пути.

https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Answer 3

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

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