Шаблон:50-51 вопрос из теста 2004 — различия между версиями

Версия 15:30, 13 ноября 2024

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

Input

Ориентированный граф , где

Стоимость для любых , где и если только

Definition

длина кратчайшего пути от до для всех

Если нет пути от до , то

Если для любого

Problem

Определить для любого

Алгоритм Флойда-Уоршалла дает динамическое программирование для решения задачи путем определения массива для и по следующим условиям

это длина кратчайшего пути от до , при которой все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если

Тогда

Алгоритм вычисляет используя рекуррентность по , где начальный шаг задается следующим образом

для и

для любого