ГДЗ по информатике, 11 класс, Босова, номер 11.2: Моделирование на графах
Информатика — Босова Л.Л., Босова А.Ю.
Дмитрий Орлов, преподаватель информатики Шпаргача обновлено 8 сентября 2026
Условие
Используя алгоритм Дейкстры, найти кратчайший путь от вершины A до вершины G по графу с весами рёбер: A-B=23, A-C=12, B-C=25, B-E=22, B-H=35, C-D=19, E-F=23, E-G=14, F-D=20, F-G=24, H-G=16.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
План решения. Для поиска кратчайшего пути от вершины A до вершины G применим алгоритм Дейкстры. Мы будем последовательно определять минимальное расстояние от стартовой вершины A до всех остальных вершин графа, пока не достигнем целевой вершины G. На каждом шаге выбираем непосещённую вершину с наименьшим текущим расстоянием и обновляем расстояния до её соседей.
Вычисление.
- Инициализация: расстояние до A равно 0, до всех остальных вершин — бесконечность (∞). Предыдущие вершины неизвестны.
- Рассматриваем вершину A (расстояние 0).
- Сосед B: d(B)=min(∞,0+23)=23. Предок B — A.
- Сосед C: d(C)=min(∞,0+12)=12. Предок C — A.
- Рассматриваем вершину C (расстояние 12).
- Сосед B: d(B)=min(23,12+25)=23. Расстояние не изменилось, предок остаётся A.
- Сосед D: d(D)=min(∞,12+19)=31. Предок D — C.
- Рассматриваем вершину B (расстояние 23).
- Сосед E: d(E)=min(∞,23+22)=45. Предок E — B.
- Сосед H: d(H)=min(∞,23+35)=58. Предок H — B.
- Рассматриваем вершину D (расстояние 31).
- Сосед F: d(F)=min(∞,31+20)=51. Предок F — D.
- Рассматриваем вершину E (расстояние 45).
- Сосед F: d(F)=min(51,45+23)=51. Расстояние не изменилось, предок остаётся D.
- Сосед G: d(G)=min(∞,45+14)=59. Предок G — E.
- Рассматриваем вершину F (расстояние 51).
- Сосед G: d(G)=min(59,51+24)=59. Расстояние не изменилось, предок остаётся E.
- Рассматриваем вершину G (расстояние 59). Это целевая вершина, алгоритм можно завершить.
Проверка и восстановление пути. Кратчайшее расстояние до G равно 59. Восстановим путь, двигаясь от G к A через предков:
- G пришла из E (вес ребра E-G=14).
- E пришла из B (вес ребра B-E=22).
- B пришла из A (вес ребра A-B=23).
- A→C→D→F→G: 12+19+20+24=75.
- A→C→D→F→E→G: 12+19+20+23+14=88.
- A→B→H→G: 23+35+16=74.
Кратчайший путь: A→B→ E→G длина 59
В условии дан полный список рёбер. Алгоритм Дейкстры применён корректно. Важно отметить, что при посещении вершины E мы обновляем расстояние до G как 59. При посещении вершины F (которая имеет расстояние 51) мы проверяем ребро F-G (вес 24), получая 51+24=75, что больше 59, поэтому предок G не меняется. Также проверено ребро H-G, но путь через H длиннее.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 11.2 из моего учебника?
Номер совпадает с учебником «Информатика», Босова Л.Л., Босова А.Ю.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 11.2?
Краткий ответ: Кратчайший путь: A B→ E G длина 59.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Информатика», Босова Л.Л., Босова А.Ю.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 11. Моделирование на графах.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.