Упр.43 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)
Рассмотрим вариант решения задания из учебника Босова 9 класс, Просвещение: 43. Рассмотрите рисунок. Кружками обозначены вершины графа; в кружки вписаны имена вершин. Вершины соединены линиями (ребрами графа); над ребрами обозначены их веса — длины пути. Рядом с каждой вершиной указана метка — длина кратчайшего пути в эту вершину из вершины А: для вершины А — это 0, для всех других вершин она пока неизвестна и обозначена знаком оо («бесконечность»). Найдите кратчайшее расстояние от вершины А до всех остальных вершин графа, действуя в соответствии с приведенным ниже алгоритмом Дейкстры. 1. Обведите вершину А, имеющую минимальную метку (0). Укажите ее соседей — вершины, в которые идут ребра из вершины А: Соседи А: B, D, C; 2. Установите очередность соседних с А вершин (по возрастанию длины пути между А и соседней вершиной): 1) первой по очереди идет вершина _, потому что длина пути между А и _ является минимальной; 2) второй по очереди идет вершина _ 3) третьей по очереди идет вершина _ 1) первой идет вершина В, длина пути между А и В является минимальной; 2) второй по очереди идет вершина D; 3) третьей по очереди идет вершина С. 3. В порядке установленной выше очередности измените метки для соседних с А вершин: вычислите сумму метки вершины А (обведенной вершины) и длины ребра, идущего из нее в очередную соседнюю вершину; если полученная сумма меньше текущей метки очередной вершины, то эту сумму запишите в качестве метки очередной вершины. После просмотра всех соседей вершины А вычеркните ее из графа. В место знака бесконечность ставим метки вершинам, равным их расстояниям от А, т.к. метка А равно 0: В – 5; D – 10; C – 15. 4. Повторите действия 1-3 для оставшихся вершин, каждый раз выбирая из них вершину, имеющую минимальную метку. Кратчайшее расстояние из А в В равно из А в С равно из А в D равно из А в Е равно из А в А равно Вершина, имеющая минимальную метку (после исключения А) это В. Ее соседи D и Е. Для D метку не меняем, т.к. 5+9 больше 10. Для Е устанавливаем метку 14+5=19. Далее по алгоритму, исключаем В, и рассматриваем вершину с минимальной следующей меткой, это D. Согласно алгоритму, устанавливаем метку для F. Она получается 10+8=18. И меняем метку для С, т.к. 10+3=13, а метка С 15. Кратчайшее расстояние: Из А в В равно 5; Из А в С равно 13; Из А в D равно 10; Из А в Е равно 19; Из А в F равно 18.
Применим алгоритм Дейкстры к графу.
Соседи вершины A: B, D, C.
Упорядочим их по возрастанию длины ребра от вершины A:
- первая — вершина B, так как $$AB=5$$;
- вторая — вершина D, так как $$AD=10$$;
- третья — вершина C, так как $$AC=15$$.
После обработки вершины A получаем метки:
$$B=5,\quad D=10,\quad C=15.$$
Далее выбираем вершину с минимальной меткой среди невычеркнутых — это B.
Соседи вершины B: D и E.
Проверяем новые расстояния:
- до D: $$5+9=14$$, это больше текущей метки $$10$$, значит метка не меняется;
- до E: $$5+14=19$$, значит $$E=19$$.
Теперь минимальная метка у вершины D. Её соседи — C, E, F.
Проверяем:
- до C: $$10+3=13$$, значит метка C уменьшается до $$13$$;
- до E: $$10+10=20$$, это больше текущей метки $$19$$;
- до F: $$10+8=18$$, значит $$F=18$$.
Оставшиеся метки уже не улучшаются, поэтому кратчайшие расстояния от вершины A такие:
$$A=0,\quad B=5,\quad C=13,\quad D=10,\quad E=19,\quad F=18.$$
Ответ
$$A=0,\ B=5,\ C=13,\ D=10,\ E=19,\ F=18.$$
