Akazikov в 15:42, 16 ноября 2024

2024-11-16T15:42:05Z

Akazikov: Новая страница: «Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом '''Input'…»

2024-11-13T15:30:19Z

Новая страница: «Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом '''Input'…»

Новая страница

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

'''Input'''

Ориентированный граф <m>G(V, E)</m>, где <m>V = {1, 2, ..., n}</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'''

<m>D(i, j)</m> длина кратчайшего пути от <m>i</m> до <m>j</m> для всех <m>i, j \in V </m>

Если нет пути от <m>i</m> до <m>j</m>, то <m>D(i, j) =\infty </m>

Если <m>i = j</m> для любого <m>i, j \in V </m>

'''Problem'''

Определить <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>i</m> до <m>j</m>, при которой все промежуточные узлы на этом пути находятся в <m>{1, 2, ..., k}</m> (где никакие промежуточные узлы не допускаются, если <m>k = 0)</m>''

Тогда <m>D(i, j) = A(n, i, j)</m>

Алгоритм вычисляет <m>A(k, i, j)</m> используя рекуррентность по <m>k</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>i \in V</m>

@@ Строка 1: / Строка 1: @@
-Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом
+Задача о кратчайшем пути для всех пар может быть определена следующим образом
 '''Input'''
-Ориентированный граф <m>G(V, E)</m>, где <m>V = {1, 2, ..., n}</m>
+Направленный граф <m>G(V, E)</m>, где <m>V = {1, 2, ..., n}</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>
+Стоимость <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'''
@@ Строка 13: / Строка 13: @@
 Если нет пути от <m>i</m> до <m>j</m>, то <m>D(i, j) =\infty </m>
-Если <m>i = j</m> для любого <m>i, j \in V </m>
+Если <m>i = j</m> для всех <m>i, j \in V </m>
 '''Problem'''
-Определить <m>D(i, j)</m> для любого <m>i, j \in V </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> 0 \le k \le n</m> и <m>i, j \in V </m> по следующим условиям
-''<m>A(k, i, j)</m> это длина кратчайшего пути от <m>i</m> до <m>j</m>, при которой все промежуточные узлы на этом пути находятся в <m>{1, 2, ..., k}</m> (где никакие промежуточные узлы не допускаются, если <m>k = 0)</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>
@@ Строка 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) = 0 </m> для любого <m>i \in V</m>
+<m>A(0, i, j) = 0 </m> для всех <m>i \in V</m>

Шаблон:50-51 вопрос из теста 2004 - История изменений

Akazikov в 15:42, 16 ноября 2024

Akazikov: Новая страница: «Задача о кратчайшем пути для всех пар может быть сформулирована следующим образом '''Input'…»