Изменения

Задан граф. Требуется дойти от некоторой начальной вершины $S$ до конечной $T$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$, т.е. путь $S \rightsquigarrow U$, пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. То есть, чтобы путь $S \rightsquigarrow T$ был оптимальным, нужно чтобы префиксы перед $T$ оптимальными, иными словами, оптимальные префиксы путей между соседними вершинами составляют оптимальный путь от начальной вершины до конечной.