ну а допустим мы имеем такие длины ребер:

.
Ну? На

вешается метка

, на

—

,

вычёркивается. Минимальная метка на

, смотрим на пути из неё — один путь в

, сумма меток меньше текущей метки в

, потому вешаем на

метку

,

вычёркивается. Минимальная метка на

, путей нет,

вычёркивается. Всё вычеркнуто, конец.
-- Вт янв 20, 2015 13:28:08 --Тогда выходят для неориентированного графа отрицательные грани - не помеха алгоритму дейкстры?
Отрицательный цикл?