Изменения

<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$ на кратчайшиетоже не может существовать, так как добраться, например, от вершины $i$ до $k$ по вершинам из множества \left \{ 1, 2, \dots, k \right \} невозможно. Тогда сам Но этого быть не может по тому, как мы определили путь $p$ не будет кратчайшим, что является противоречием.Во время работы алгоритма будут просмотрены все возможные разбиения на соответствующие пути для каждой пары вершин и выбран лучший из них, при возможности, будет построен путь. По его окончании транзитивное замыкание будет построено корректно.