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 & 0end{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{qquadquad} 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 & 0end{pmatrix}$