2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 13:25 
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 писал(а):
Тогда выходят для неориентированного графа отрицательные грани - не помеха алгоритму дейкстры?
Отрицательный цикл?

 
 
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 14:24 
greg2 в сообщении #965340 писал(а):
Почему нельзя применять на графах с ребрами отрицательный длины? Нигде не нашёл объяснению этому,

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

 
 
 [ Сообщений: 17 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group