Шаблон:50-51 вопрос из теста 2004 — различия между версиями
Материал из DISCOPAL
Akazikov (обсуждение | вклад) (Новая страница: «Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом '''Input'…») |
Akazikov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Задача о кратчайшем пути для всех пар может быть | + | Задача о кратчайшем пути для всех пар может быть определена следующим образом |
'''Input''' | '''Input''' | ||
| − | + | Направленный граф <m>G(V, E)</m>, где <m>V = {1, 2, ..., n}</m> | |
| − | Стоимость <m>C(i, j)\in\mathbb{R}^+\cup{\infty}</m> для | + | Стоимость <m>C(i, j)\in\mathbb{R}^+\cup{\infty}</m> для всех <m>i, j \in V </m>, где <m>C(i, j) =\infty </m> тогда и только тогда, когда <m>(i, j) \in E</m> |
'''Definition''' | '''Definition''' | ||
| Строка 13: | Строка 13: | ||
Если нет пути от <m>i</m> до <m>j</m>, то <m>D(i, j) =\infty </m> | Если нет пути от <m>i</m> до <m>j</m>, то <m>D(i, j) =\infty </m> | ||
| − | Если <m>i = j</m> для | + | Если <m>i = j</m> для всех <m>i, j \in V </m> |
'''Problem''' | '''Problem''' | ||
| − | Определить <m>D(i, j)</m> для | + | Определить <m>D(i, j)</m> для всех <m>i, j \in V </m> |
| − | Алгоритм Флойда-Уоршалла дает | + | Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива <m>A(k, i, j)</m> для <m> 0 \le k \le n</m> и <m>i, j \in V </m> по следующим условиям |
| − | ''<m>A(k, i, j)</m> | + | ''<m>A(k, i, j)</m> длина кратчайшего пути от <m>i</m> до <m>j</m>, для которого все промежуточные узлы на этом пути находятся в <m>{1, 2, ..., k}</m> (где никакие промежуточные узлы не допускаются, если <m>k = 0)</m>'' |
Тогда <m>D(i, j) = A(n, i, j)</m> | Тогда <m>D(i, j) = A(n, i, j)</m> | ||
| Строка 29: | Строка 29: | ||
<m>A(0, i, j) = C(i, j)</m> для <m>i, j \in V</m> и <m>i \ne j</m> | <m>A(0, i, j) = C(i, j)</m> для <m>i, j \in V</m> и <m>i \ne j</m> | ||
| − | <m>A(0, i, j) = 0 </m> для | + | <m>A(0, i, j) = 0 </m> для всех <m>i \in V</m> |
Текущая версия на 15:42, 16 ноября 2024
Задача о кратчайшем пути для всех пар может быть определена следующим образом
Input
Направленный граф , где
Стоимость для всех , где тогда и только тогда, когда
Definition
длина кратчайшего пути от до для всех
Если нет пути от до , то
Если для всех
Problem
Определить для всех
Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива для и по следующим условиям
длина кратчайшего пути от до , для которого все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если
Тогда
Алгоритм вычисляет используя рекуррентность по , где начальный шаг задается следующим образом
для и
для всех