Математика, вопрос задал gerasimyuk2011 , 7 лет назад

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

Приложения:

Ответы на вопрос

Ответил Indentuum

Составим матрицу смежности $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}$

Предыдущий вопрос

Следующий вопрос

Новые вопросы

Английский язык, 1 год назад

What are you going to be ? как почитать этот текст What are you going to be ? ll be a teacher, Thats the life me . What are you going to be ? What are you going to be ?

Русский язык, 1 год назад

что такое деепричастный оборот? и деепричастие?

Геометрия, 7 лет назад

Найдите площадь прямоугольного треугольника,если гипотенуза равна 41 см,а один из катетов 9 см...

Физика, 7 лет назад

Определите массу медной заготовки кубической формы с длиной стороны 5 м...

Математика, 8 лет назад

Lim( x стремится к бесконечности) (1+4x)^1/4x...

Алгебра, 8 лет назад

(2,73+4,81+3,27-2,81):(2/5-14/15):25*37*0,4=...