Логика обновления Floyd fullPath (не рекурсивный алгоритм)

1. Ключевой момент алгоритма Флойда заключается в использовании промежуточных узлов для оптимизации пути от исходного узла v к конечному узлу u.

2. Когда найден промежуточный узел k, который можно оптимизировать, он вставляется между исходным узлом v и конечным узлом u (v->k(промежуточный узел)->u).

3. В этот момент необходимо обратить внимание на то, что путь v->k может иметь промежуточные узлы, которые можно оптимизировать, а путь k->u также может иметь такие узлы. Необходимо выполнить две задачи: 1) постоянно искать промежуточные узлы для вставки в путь; 2) убедиться, что каждый сегмент не имеет промежуточных узлов, которые могут быть оптимизированы дальше.

4. Как гарантировать, что все промежуточные узлы будут записаны? Условие отсутствия промежуточных узлов, подлежащих дальнейшей оптимизации, выглядит следующим образом: R(path(index), path(index+1)) == path(index+1).

5. Устанавливается индекс, который записывает уже выполненную оптимизацию, и rNum, который записывает количество промежуточных узлов (для удобства вставки новых промежуточных узлов). Постоянно ищутся промежуточные узлы между вершинами index и index+1 и вставляются между ними. Если между вершинами index и index+1 нет промежуточных узлов (R(index, index+1)==index+1), то индекс увеличивается на единицу, чтобы обновить промежуточные узлы следующего уровня между index и index+1. Таким образом, оптимизация продолжается непрерывно, индекс продвигается вперёд. Наконец, когда все пути больше не имеют промежуточных узлов, которые можно добавить (path(index+1)==u), это означает, что оптимизация достигла конечной точки и поиск пути завершён.