Для данного ориентированного взвешенного графа, имеющего одно отрицательное ребро (u, v), найти кратчайший путь (s, t)

Вы можете использовать информацию о наличии единственного отрицательного края для создания эффективного алгоритма.

Обозначим как a исходный узел отрицательного края и b узел назначения, так что у нас есть отрицательный край a -> b.

Есть два вида путей от узла s к узлу t:

1. край a->b не является частью пути;
2. край a->b является частью пути.

Мы намерены найти кратчайший путь от s до t, и мы сделаем это, найдя кратчайший путь каждого из двух вышеуказанных типов.

Минимальный путь вдоль линий типа (1) можно найти, просто применив алгоритм Дейкстры к модифицированному графу, в котором удалено отрицательное ребро.

Для типа (2) теперь нас интересует кратчайший путь от s до t, который содержит ребро a->b. Этот путь должен иметь следующую форму: s -> ... -> a -> b -> ... -> t.

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

В этой ситуации (без отрицательных циклов) мы можем применить алгоритм Дейкстры дважды, сначала чтобы найти кратчайший путь от s до a; а затем найти кратчайший путь от b до t. В обоих случаях алгоритм Дейкстры следует применить к графу, измененному путем удаления отрицательного ребра a->b.

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

Однако можно определить, есть ли такой цикл на графе, снова используя алгоритм Дейкстры. Обратите внимание: поскольку существует единственный отрицательный край, a->b, отрицательный цикл должен содержать его. Таким образом, нам нужен путь от b к a, общая стоимость которого меньше абсолютного значения веса a->b. Мы можем проверить, существует ли такой путь, применив алгоритм Дейкстры с начальным узлом b и пунктом назначения a. Опять же, алгоритм Дейкстры должен быть применен к графу с удаленным ребром a->b (нас не интересует его наличие на пути), поэтому все веса ребер положительны.