Помогите решить теорию алгоритмов 6 вариант

Question

Дан 1 ответ

Правильный ответ

Составим матрицу смежности $M$ .

$M = \begin{pmatrix} 0 & 4 & 4 & \infty & 3 \\ 2 & 0 & 8 & \infty& \infty \\ \infty & \infty & 0 & 5 & 5 \\ \infty & \infty & 8 & 0 & \infty \\ \infty & \infty & 4 & 4 & 0\end{pmatrix}$

Где $\infty$ означает отстутствие пути (ребра) между вершинами.

Составим по ней матрицу кратчайших путей $D$ .

Пусть $D = M$ , а $D_{uv}$ - длина пути из $u$ в $v$ .

Пусть $V = \{ A, B, C, D, E\}$ - множество вершин.

Рассмотрим вершины $k,u,v \in V$ . Если кратчайший путь между $u$ и $v$ проходит через вершину $k$ , то $M_{uk} + M_{kv} \leq M_{uv}$ , иначе, M_{uv}" alt="M_{uk} + M_{kv} > M_{uv}" align="absmiddle" class="latex-formula">. Тогда $D_{uv} = \min(D_{uv}, D_{uk} + D_{kv})$ .

Составим алгоритм на псевдокоде:

$\textrm{for } k \in V \textrm{ do}\\\textrm{\quad for } u \in V \textrm{ do}\\\textrm{\qquad for } v \in V \textrm{ do}\\\textrm{\qquad\quad} D_{uv} = \min(D_{uv}, D_{uk} + D_{kv})$ .

Вообще, сложность алгоритма $O(n^3)$ и при $n = 5$ , количество операций $\approx 5^3 = 125$ . Делать 125 сравнений - несколько много. Приведу лишь итоговую матрицу:

$D = \begin{pmatrix} 0 & 4 & 4 & 7 & 3 \\ 2 & 0 & 6 & 9 & 5 \\ \infty & \infty & 0 & 5 & 5 \\ \infty & \infty & 8 & 0 & 13 \\ \infty & \infty & 4 & 4 & 0\end{pmatrix}$

Indentuum_zn (4.7k баллов) 26 Май, 20