Упр.43 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)
Решение #1
Рассмотрим вариант решения задания из учебника Босова 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.
*размещая тексты в комментариях ниже, вы автоматически соглашаетесь с пользовательским соглашением
