Страница 42 номер 43, ГДЗ по информатике за 9 класс к рабочей тетради Босовой. Решение с ответом к РТ

Номер 43. Рассмотрите рисунок. Кружками обозначены вершины графа; в кружки вписаны имена вершин. Вершины соединены линиями (ребрами графа); над ребрами обозначены их веса — длины пути. Рядом с каждой вершиной указана метка — длина кратчайшего пути в эту вершину из вершины A: для вершины A — это 0, для всех других вершин она пока неизвестна и обозначена знаком ∞ («бесконечность»).
Найдите кратчайшее расстояние от вершины A до всех остальных вершин графа, действуя в соответствии с приведенным ниже алгоритмом Дейкстры.
1. Обведите вершину A, имеющую минимальную метку (0).
Укажите ее соседей — вершины, в которые идут ребра из вершины A:
2. Установите очередность соседних с A вершин (по возрастанию длины пути между A и соседней вершиной):
1) первой по очереди идет вершина, потому что длина пути между A и является минимальной;
2) второй по очереди идет вершина;
3) третьей по очереди идет вершина.
3. В порядке установленной выше очередности измените метки для соседних с A вершин: вычислите сумму метки вершины A (обведенной вершины) и длины ребра, идущего из нее в очередную соседнюю вершину; если полученная сумма меньше текущей метки очередной вершины, то эту сумму запишите в качестве метки очередной вершины.
После просмотра всех соседей вершины A вычеркните ее из графа.
4. Повторите действия 1-3 для оставшихся вершин, каждый раз выбирая из них вершину, имеющую минимальную метку.