Просмотр исходного текста страницы Шаблон:50-51 вопрос из теста 2004

Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом

'''Input'''

Ориентированный граф <m>G(V, E)</m>, где <m>V = {1, 2, ..., n}</m>

Стоимость <m>C(i, j)\in\mathbb{R}^+\cup{\infty}</m> для любых <m>i, j \in V </m>, где <m>C(i, j) =\infty </m> и если только <m>(i, j) \in E</m>

'''Definition'''

<m>D(i, j)</m> длина кратчайшего пути от <m>i</m> до <m>j</m> для всех <m>i, j \in V </m>

Если нет пути от <m>i</m> до <m>j</m>, то <m>D(i, j) =\infty </m>

Если <m>i = j</m> для любого <m>i, j \in V </m>

'''Problem'''

Определить <m>D(i, j)</m> для любого <m>i, j \in V </m>

Алгоритм Флойда-Уоршалла дает динамическое программирование для решения задачи путем определения массива <m>A(k, i, j)</m> для <m> 0 \le k \le n</m> и <m>i, j \in V </m> по следующим условиям

''<m>A(k, i, j)</m> это длина кратчайшего пути от <m>i</m> до <m>j</m>, при которой все промежуточные узлы на этом пути находятся в <m>{1, 2, ..., k}</m> (где никакие промежуточные узлы не допускаются, если <m>k = 0)</m>''

Тогда <m>D(i, j) = A(n, i, j)</m>

Алгоритм вычисляет <m>A(k, i, j)</m> используя рекуррентность по <m>k</m>, где начальный шаг задается следующим образом

<m>A(0, i, j) = C(i, j)</m> для <m>i, j \in V</m> и <m>i \ne j</m>

<m>A(0, i, j) = 0 </m> для любого <m>i \in V</m>