Шаблон:50-51 вопрос из теста 2004
Материал из DISCOPAL
Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом
Input
Ориентированный граф , где
Стоимость для любых , где и если только
Definition
длина кратчайшего пути от до для всех
Если нет пути от до , то
Если для любого
Problem
Определить для любого
Алгоритм Флойда-Уоршалла дает динамическое программирование для решения задачи путем определения массива для и по следующим условиям
это длина кратчайшего пути от до , при которой все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если
Тогда
Алгоритм вычисляет используя рекуррентность по , где начальный шаг задается следующим образом
для и
для любого
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.