Поиск самого дешевого пути с игнорированием одной стоимости

Я хочу найти самый дешевый путь между 2 вершинами, и я могу выбрать один путь, который я могу пройти бесплатно., например:

Введите описание изображения здесь

Самый дешевый путь между вершинами 1 и 6-1-3-4-5-6 - я иду по краю 1-3 (стоимость 30) бесплатно, и это дает мне общую стоимость 21.

Есть ли другой способ, кроме проверки всех путей по одному?

1 5
path dijkstra depth-first-search

1 ответ:

Один из способов сделать это - сделать следующее:

  1. дублируйте свой граф, чтобы у вас был исходный граф G с узлами 1,2 и т. д. и копия G 'с узлами 1', 2'и т. д. и соответствующие ребра.
  2. для каждого ребра (a,b) G сделайте дугу (направленную!) от a до b' и еще один от b до a', оба со стоимостью 0.
    3. Наконец, используйте любой алгоритм кратчайшего пути из любой вершины подграфа G в любую вершину G' (от 1 до 6' в вашем примере).

В основном, что происходит это то, что вы переключаетесь с подграфа G на G', когда используете свой джокер.

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

4