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