Шаблон:50-51 вопрос из теста 2004

Материал из DISCOPAL
Версия от 15:30, 13 ноября 2024; Akazikov (обсуждение | вклад) (Новая страница: «Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом '''Input'…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Input

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

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

Definition

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

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

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

Problem

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

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

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

Тогда

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

для и

для любого

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.