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

Версия 20:24, 11 января 2025

Какие из следующих задач известны как решаемые за время ?

I. Найти кратчайший путь от заданной начальной вершины до заданной конечной вершины в направленном графе с n вершинами и неотрицательными целочисленными весами на рёбрах.
II. Найти самый длинный простой путь от заданной начальной вершины до заданной конечной вершины в направленном графе с n вершинами и неотрицательными целочисленными весами на рёбрах.
III. Найти самый длинный путь от заданной начальной вершины до заданной конечной вершины в ациклическом направленном графе (DAG) с n вершинами и неотрицательными целочисленными весами на рёбрах.

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

Разберём каждое из утверждений:

I. (кратчайший путь): Можно решить за с помощью алгоритма Флойда–Уоршелла.
II. (длиннейший простой путь): Задача NP-полная и не решается за полиномиальное время в общем случае.
III. (длиннейший путь в DAG): Можно решить за с помощью динамического программирования или топологической сортировки.

Только I и III укладываются в .

Задача зарезервирована: Nikitashapovalov 20:44, 8 января 2025 (UTC)

@@ Строка 18: / Строка 18: @@
 {{cstest-source|2011-gre-cs-practice-book.pdf|43|61}}
+Разберём каждое из утверждений:
+* I. (кратчайший путь): Можно решить за <m>O(n^3)</m> с помощью алгоритма Флойда–Уоршелла.
+* II. (длиннейший простой путь): Задача NP-полная и не решается за полиномиальное время в общем случае.
+* III. (длиннейший путь в DAG): Можно решить за <m>O(n^3)</m>  с помощью динамического программирования или топологической сортировки.
+Только I и III укладываются в <m>O(n^3)</m>.
 {{question-ok|}}
 {{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:44, 8 января 2025 (UTC)}}