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

Question

Рассмотрим задачу о кратчайшем пути на орграфе G = (V, A, W), возможно, с отрицательными циклами. Мы рассматриваем только простые пути, т.е. пути без повторяющихся вершин. Построив новый граф G '(V, A, W') такой, что G 'и G имеют одинаковые вершины и дуги, но для каждого ar c его вес в G' больше, чем его вес в G на постоянная.

Ясно, что если P1 и P2 - два пути, и w (P1)

Более того, проблема кратчайшего пути с отрицательными циклами на самом деле NP-hard . Если я был прав, и мы можем свести случай с отрицательными циклами к случаю без отрицательных циклов, разве проблема не должна быть полиномиальной?

Я предполагаю, что что-то упустил, но я не уверен, что.

Answer 1

Понятно, если P ₁ и P ₂ - это два пути, а w (P *) 1011 * 1 ) 2 ) in G , затем w '(P ₁ ) 2 ) в G '. Это означает, что кратчайший путь в G также является кратчайшим путем в G '.

Нет , так как если вес пути p в G обозначается как w _p , тогда вес этого пути в G ' равен w _p + n _p × c с n _p количество ребер в пути и c константа с которой вы увеличиваете каждое ребро.

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

Take например, следующий график:

 A               B
 o-------7-------o
1 \             / 1
   o--2--o--2--o
   C     D     E

Здесь кратчайший путь между A и B проходит через C, D и E, поскольку сумма равна 1 + 2 + 2 + 1 = 6 , тогда как прямой путь между A и B приведет к 7 .

Если мы теперь увеличим каждое ребро, например, на два получаем:

 A               B
 o-------9-------o
3 \             / 3
   o--4--o--4--o
   C     D     E

Итак, теперь путь A- C -DEB имеет вес 3 + 4 + 4 + 3 = 14 , тогда как прямой путь AB имеет вес 9 . Поэтому, если мы увеличиваем каждое ребро с определенной константой, оптимальный путь может быть другим.