Упр.3.43 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

Рассмотрим граф и применим алгоритм Дейкстры.

1. Начинаем с вершины A: её метка равна $$0$$.
2. Соседи вершины A: B, D, C.
3. Вычисляем новые метки:
   • для B: $$0+5=5$$;
   • для D: $$0+10=10$$;
   • для C: $$0+15=15$$.
4. Выбираем вершину с минимальной меткой среди непосещённых — это B ($$5$$). Её соседи: D и E.
   • для D: $$5+9=14$$, но текущая метка $$10$$ меньше, значит оставляем $$10$$;
   • для E: $$5+14=19$$, значит метка E равна $$19$$.
5. Следующая вершина с минимальной меткой — D ($$10$$). Её соседи: C, E, F.
   • для C: $$10+3=13$$, значит метка C становится $$13$$;
   • для E: $$10+10=20$$, но уже есть $$19$$, поэтому не меняем;
   • для F: $$10+8=18$$, значит метка F равна $$18$$.
6. Остаётся вершина C с меткой $$13$$, затем F с меткой $$18$$ и E с меткой $$19$$.

Итак, кратчайшие расстояния от вершины 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$$.