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

[Nemiroff]

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

ну а допустим мы имеем такие длины ребер: $SA=3, SB=1, BA=1$.

Ну? На $A$ вешается метка $(3,S)$, на $B$ — $(1,S)$, $S$ вычёркивается. Минимальная метка на $B$, смотрим на пути из неё — один путь в $A$, сумма меток меньше текущей метки в $A$, потому вешаем на $A$ метку $(2,B)$, $B$ вычёркивается. Минимальная метка на $A$, путей нет, $A$ вычёркивается. Всё вычеркнуто, конец.

-- Вт янв 20, 2015 13:28:08 --

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

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

Отрицательный цикл?

[sqribner48]

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

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

В доказательстве правильности работы алгоритма Дейкстры существенным образом используется условие неотрицательности весов ребер (в противном случае не удалось бы доказать правильность работы алгоритма). Посмотрите, например, книгу: Н. Кристофидес. Теория графов. Алгоритмический подход. М: Мир,1978. на стр. 178.