Question

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

Answer 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_{uk} + M_{kv} > M_{uv}$. Тогда  $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}$