Изменения

Префикс оптимального пути из $S \rightsquigarrow U$ является оптимальным путём из $S \rightsquigarrow U$.Требуется дойти до $T$. Оптимальный путь проходит через $U$. Пусть префикс $dU$ неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь от $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется.