Определите чему будет равна 2-ая строка массива A (кратчайших расстояний) в алгоритме Флойда после k = 2. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по программированию
Определите чему будет равна 2-ая строка массива A (кратчайших расстояний) в алгоритме Флойда после k = 2

Определите чему будет равна 2-ая строка массива A (кратчайших расстояний) в алгоритме Флойда после k = 2 .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Определите, чему будет равна 2-ая строка массива A (кратчайших расстояний) в алгоритме Флойда после k = 2. Алгоритм Флойда (алгоритм Флойда–Уоршелла) — алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе.

Ответ

v2 ∞ - 7 2 16

Решение

Потяни, чтобы посмотреть

Составим матрицу D0 – матрица расстояний рёбер и матрицу S0.
k=0
D0 v1 v2 v3 v4 v5
S0 v1 v2 v3 v4 v5
v1 - 2 10 6 ∞
v1 - 2 3 4 5
v2 ∞ - 7 2 ∞
v2 1 - 3 4 5
v3 ∞ ∞ - ∞ 9
v3 1 2 - 4 5
v4 ∞ ∞ 3 - ∞
v4 1 2 3 - 5
v5 3 ∞ ∞ 11 -
v5 1 2 3 4 -
k=1. Выделяем строку и столбец с номером k в предыдущих матрицах . Выделим красным те элементы матрицы Dk-1 и Sk-1, где dij>dki+djk. В матрице Dk заменяем красные элементы на dki+djk, в Sk на k. Повторяем аналогичные действия для k+1 до k=n – число вершин.
D1 v1 v2 v3 v4 v5
S1 v1 v2 v3 v4 v5
v1 - 2 10 6 ∞
v1 - 2 3 4 5
v2 ∞ - 7 2 ∞
v2 1 - 3 4 5
v3 ∞ ∞ - ∞ 9
v3 1 2 - 4 5
v4 ∞ ∞ 3 - ∞
v4 1 2 3 - 5
v5 3 5 13 9 -
v5 1 1 1 1 -
k=2
D2 v1 v2 v3 v4 v5
S2 v1 v2 v3 v4 v5
v1 - 2 9 4 ∞
v1 - 2 2 2 5
v2 ∞ - 7 2 ∞
v2 1 - 3 4 5
v3 ∞ ∞ - ∞ 9
v3 1 2 - 4 5
v4 ∞ ∞ 3 - ∞
v4 1 2 3 - 5
v5 3 5 12 7 -
v5 1 1 2 2 -
k=3
D3 v1 v2 v3 v4 v5
S3 v1 v2 v3 v4 v5
v1 - 2 9 4 18
v1 1 2 2 2 3
v2 ∞ - 7 2 16
v2 1 2 3 4 3
v3 ∞ ∞ - ∞ 9
v3 1 2 3 4 5
v4 ∞ ∞ 3 - 12
v4 1 2 3 4 3
v5 3 5 12 7 -
v5 1 1 2 2 3
Ответ:
v2 ∞ - 7 2 16

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу