Question

Решите как можно быстрее с объяснением Желательно

Answer 1

Ответ:

59

Объяснение:

Вспомним алгоритм Дейкстры:

1) В начале алгоритма расстояние до начальной вершины 0, до остальных вершин бесконечность (расстояния считаются от начальной вершины). Все вершины считаются непосещенными.

2) Пока есть непосещенные вершины, выбирается одна из них с минимальным расстоянием. Затем рассматривается, куда и за сколько можно перейти по ребрам из этой вершины, назовем это расстояние Х. Если Х меньше, чем текущий найденный путь, обновим его.

3) После окончания алгоритма, расстояние, найденное для искомой вершины - ответ.

Перейдем к примеру, таблица расстояний и посещений выглядит так:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&\infty&\infty&\infty&\infty&\infty&\infty&\infty\\-&-&-&-&-&-&-&-\end{array}\right]$

(Первая строка - название вершины; вторая - расстояние от А; третья - посетили мы ее или нет)

1) Берем минимальное расстояние среди непосещенных вершин - это столбец А. Из нее есть два ребра АВ и АС: расстояние из А + АВ = 0 + 23 = 23. Это лучше, чем бесконечность, обновим расстояние до В. Аналогично, расстояние до С станет равно 12:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&\infty&\infty&\infty&\infty&\infty\\+&-&-&-&-&-&-&-\end{array}\right]$

2) Берем минимальное расстояние среди непосещенных вершин - это столбец С. Из С выходит три ребра:

• СА: 12 (расстояние от А до С) + 12 (длина СА) = 24. Сейчас расстояние до А равно 0, что меньше, чем 24 - расстояние не обновляется

• СВ: 12 (расстояние от А до С) + 25 (длина СВ) = 37. Сейчас расстояние до В равно 23, что меньше, чем 37 - расстояние не обновляется

• СD:  12 (расстояние от А до С) + 19 (длина СD) = 31. Сейчас расстояние до D равно ∞, что больше, чем 31 - расстояние обновляется

Теперь таблица выглядит так:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&\infty&\infty&\infty&\infty\\+&-&+&-&-&-&-&-\end{array}\right]$

3) Берем минимальное расстояние среди непосещенных вершин - это  вершина B. Из B выходит 4 ребра:

• BA: 23 (расстояние от А до B) + 23 (длина BА) = 46. Сейчас расстояние до А равно 0, что меньше, чем 46 - расстояние не обновляется

• BC: 23 (расстояние от А до B) + 25 (длина ВC) = 48. Сейчас расстояние до В равно 23, что меньше, чем 48 - расстояние не обновляется

• BE:  23 (расстояние от А до B) + 22 (длина BE) = 45. Сейчас расстояние до Е равно ∞, что больше, чем 45 - расстояние обновляется

• BH:  23 (расстояние от А до B) + 35 (длина BH) = 58. Сейчас расстояние до D равно ∞, что больше, чем 58 - расстояние обновляется

Теперь таблица выглядит так:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&45&\infty&\infty&58\\+&+&+&-&-&-&-&-\end{array}\right]$

4) Теперь непосещенный минимум - D. Так же рассматриваем все ребра из D и (не)обновляем расстояния. После этого шага таблица выглядит так

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&45&51&\infty&58\\+&+&+&+&-&-&-&-\end{array}\right]$

5) минимум в Е, таблица после этого шага:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&45&51&59&58\\+&+&+&+&+&-&-&-\end{array}\right]$

6) минимум в F, таблица:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&45&51&59&58\\+&+&+&+&+&+&-&-\end{array}\right]$

7) минимум в H:

$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&74&51&59&58\\+&+&+&+&+&+&-&+\end{array}\right]$

8) И последняя итерация (необязательная) из G:$\left[\begin{array}{cccccccc}A&B&C&D&E&F&G&H\\0&23&12&31&74&51&59&58\\+&+&+&+&+&+&+&+\end{array}\right]$

Смотрим число под G - это ответ, 59.