2004-gre-cs-practice-book.pdf/Q50

Ссылки сюда (2) →

Вопрос: Q50-4c9f66

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

Какой из следующих этапов является общим в рекурентной схеме, где

Ответы

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

Объяснение

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

Формулы немного пугают, но надо же помнить

• рекурсивная зависимость — от таблицы на предыдущей итерации
• и на таблицу расстояний не смотрим — выбираем минимум между известным путем и суммой путей через какой-то транзитный новый узел.

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

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

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