2
cyb12Скорее всего я вам ничем не помогу, но есть такая идея. Допустим у вас вот эта вот неудобная ситуация все-таки возникла, т.е.

оказалась на единственном пути от

до

. Тогда мы можем заменить

на

(увеличив тем самым расстояние от

до

на единицу), а в качестве

выбрать ещё неиспользованную соседку. Если до этой соседки есть более короткий путь, не проходящий через новую

, то мы приходим к ситуации из стартового сообщения (т.е. получаем более короткий простой цикл, что нарушает условие минимальности уже имеющегося), в противном же случае продолжаем процесс "передвигания"

вдоль содержащего её минимального цикла длины

пока расстояние от

до

не превысит

, т.е. пока не нарушится условие, по которому расстояние от любой вершины до

не больше

(длина минимального цикла при этом обеспечивает это запасное расстояние).
В общем тут как-то должна использоваться принадлежность

и

минимальному циклу, и в тоже время эти вершины могут выбираться не обязательно произвольно... Может быть там в статье есть какие-то дополнительные детали? Нельзя ли процитировать (особенно про то, что

и

-- любые смежные из цикла)?