Алгоритм дейкстры

[greg2]

Почему нельзя применять на графах с ребрами отрицательный длины? Нигде не нашёл объяснению этому, только упоминание, что нельзя. Самому же не получилось придумать такой пример графа, где бы он работал некорректно, поэтому приведите, пожалуйста, пример или объясните почему нельзя

[Nemiroff]

Ну попробуйте $V=\{S,A,B\}, E = \{(S,A,1), (S,B,2), (B,A,-2)\}$. Начинать из $S$.

[greg2]

И в чём некорректность? Наикратчайший путь к В через вершину А.

[Nemiroff]

greg2 в сообщении #965428 писал(а):

Наикратчайший путь к В через вершину А.

К $B$ нельзя через $A$ пробраться, нет ребра $(A,B)$. Можно наоборот.

[greg2]

А, я думла это неориентированный граф. Ну допустим, пробрались к А через B, путь равен нулю. В чем здесь проблема?

[Nemiroff]

greg2 в сообщении #965439 писал(а):

Ну допустим, пробрались к А через B, путь равен нулю. В чем здесь проблема?

В том, что Дейкстра не сможет этот путь найти.

[greg2]

Именно вот это меня интересует. Дейскстра действует так:
1) смотрим все вершины, соседствующие с S. Добавляем полученные длины.
$SA=1$
$SB=2$
2) из соседедствующих вершин можем перейти куда-нибудь только из вершины B, значит имеем
$SBA=2-2=0 \leq SA=1$, все ребра проверены, оставшиеся пути кратчайшие пути

$SBA=0, SB=2$

Разве не нашёл этот путь?

-- 20.01.2015, 13:58 --

Или здесь суть в том, что дейкстра остановится, проверив все вершины и по третьему ребру даже не пройдёт?

[provincialka]

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

[Nemiroff]

greg2 в сообщении #965449 писал(а):

1) смотрим все вершины, соседствующие с S. Добавляем полученные длины.
$SA=1$
$SB=2$

Вычёркиваем $S$. Смотрим на кратчайшего соседа — это $A$, из неё нельзя перейти, вычеркиваем её. Смотрим на $B$: у неё нет невычеркнутых соседей. Конец.

-- Вт янв 20, 2015 13:10:58 --

provincialka в сообщении #965459 писал(а):

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

Это немного не то. Одно дело нет пути, другое дело алгоритм не находит. Беллман-Форд находит путь при отрицательных весах и даже распознаёт отрицательные циклы, если я не ошибаюсь.

[provincialka]

Да, я уже сообразила.

[greg2]

Nemiroff в сообщении #965460 писал(а):

greg2 в сообщении #965449 писал(а):

1) смотрим все вершины, соседствующие с S. Добавляем полученные длины.
$SA=1$
$SB=2$

Вычёркиваем $S$. Смотрим на кратчайшего соседа — это $A$, из неё нельзя перейти, вычеркиваем её. Смотрим на $B$: у неё нет невычеркнутых соседей. Конец.

ну а допустим мы имеем такие длины ребер: $SA=3, SB=1, BA=1$. Дейкстра так же не должен будет перейти на А через B, хотя этот путь будет кратчайшим

[provincialka]

В этом случае сначала обрабатывается $B$, у нее метка меньше.

[greg2]

provincialka в сообщении #965468 писал(а):

В этом случае сначала обрабатывается $B$, у нее метка меньше.

Сначала же рассматриваются все соседи, а только потом продолжают рассматривают соседей соседей, начиная с "кратчайшего" соседа.

[provincialka]

На нулевом шаге вершине $S$ ставится в соответствие 0. Потом $A \to 3, B\to1$. Зачеркиваем $S$. Дальше что?

[greg2]

Всё, понял. Тут загвоздка в том, что это ориентированный граф и перейти с А мы никуда не можем, а с В можем. Тогда выходят для неориентированного графа отрицательные грани - не помеха алгоритму дейкстры?