В доказательстве правильности алгоритма Дейкстры есть следующая лемма:
Пусть u будет предшественником v на кратчайшем пути P: s -> ...-> u-> v от s до v. Тогда, если d (u) = δ (s, u) и ребро (u, v) расслаблен, мы имеем d (v) = δ (s, v), где функция δ (x, y) обозначает минимальный вес пути от x до y.
Интересно, зачем нам в этой лемме условие d (u) = δ (s, u). Если путь P: s -> ...-> u-> v является кратчайшим путем от s до v, то по свойству оптимальной подструктуры подпуть s -> ...-> u в P также должен быть кратчайший путь от с до вас. Следовательно, d (u) должно быть равно δ (s, u).
Существует ли случай, когда d (u) ≠ δ (s, u), но P: s -> ...-> u-> v является кратчайшим из s в v? Если да, может кто-нибудь предложить пример здесь.
Любая помощь будет оценена.