2004-gre-cs-practice-book.pdf/Q51 — различия между версиями

Текущая версия на 15:33, 15 декабря 2024

Вопрос: Q51-4c9f66

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

Input

Направленный граф , где

Стоимость для всех , где тогда и только тогда, когда

Definition

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

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

Если для всех

Problem

Определить для всех

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

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

Тогда

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

для и

для всех

Каково время работы алгоритма Флойда-Уоршалла ?

Ответы

• Правильный ответ:

Объяснение

Исходники — вопрос 51 на 35 странице книги «2004-gre-cs-practice-book.pdf»

Ну, про куб у Флойда-Уоршолла надо помнить.