Изменения

<wikitex>Назовем ''промежуточной'' вершину некоторого пути $p = \left \langle v_0, v_1, \dots, v_k \right \rangle$, принадлежащую множеству вершин этого пути и отличающуюся от начальной и конечной вершин, то есть принадлежащую $\left \{ v_1, v_2, \dots, v_{k-1} \right \}$. Рассмотрим произвольную пару вершин $i, j \in V$ и все пути между ними, промежуточные вершины которых принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k \right \}$. Пусть $p$ - кратчайший из них. Рассмотрим случаи:* $k$ не является промежуточной вершиной пути $p$. Тогда все его промежуточные пути принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$, что и требуется.* $k$ является промежуточной вершиной пути $p$. Тогда этот путь можно разбить на два пути: $i \xrightarrow{p_1} k \xrightarrow{p_2} j$. Как $p_1$, так и $p_2$ являются кратчайшими путями между соответствующими вершинами $i, k$ и $k, j$ с промежуточными вершинами из множества $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$ (так как вершина $k$ - либо конечная, либо начальная, то она не может быть в множестве по нашему определению). Действительно, если они не являются таковыми, то заменим эти подпути пути $p$ на кратчайшие. Тогда сам путь $p$ не будет кратчайшим, что является противоречием.Во время работы алгоритма будут просмотрены все возможные разбиения на соответствующие пути для каждой пары вершин и выбран лучший из них. По его окончании транзитивное замыкание будет построено корректно.