2004-gre-cs-practice-book.pdf/Q51 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q51-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q51-4c9f66 == | == Вопрос: Q51-4c9f66 == | ||
| + | {{50-51 вопрос из теста 2004}} | ||
| − | + | Каково время работы алгоритма Флойда-Уоршалла ? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>O(n)</m> |
| − | ( | + | * <m>O(n^2)</m> |
| + | * Правильный ответ: <m>O(n^3)</m> | ||
| + | * <m>O(n^3logn)</m> | ||
| + | * <m>O(n^4)</m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|35|51}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Ну, про куб у Флойда-Уоршолла надо помнить. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 15:33, 15 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Алгоритмы на графах]] | |
Текущая версия на 15:33, 15 декабря 2024
Вопрос: Q51-4c9f66
Задача о кратчайшем пути для всех пар может быть определена следующим образом
Input
Направленный граф , где
Стоимость для всех , где тогда и только тогда, когда
Definition
длина кратчайшего пути от до для всех
Если нет пути от до , то
Если для всех
Problem
Определить для всех
Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива для и по следующим условиям
длина кратчайшего пути от до , для которого все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если
Тогда
Алгоритм вычисляет используя рекуррентность по , где начальный шаг задается следующим образом
для и
для всех
Каково время работы алгоритма Флойда-Уоршалла ?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 51 на 35 странице книги «2004-gre-cs-practice-book.pdf»
Ну, про куб у Флойда-Уоршолла надо помнить.