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

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

Применим алгоритм Дейкстры к графу с вершины A.

Начальные метки: $$A=0,$$ у остальных вершин метка $$\infty.$$

Соседи вершины A: 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. Её соседи: C, E, F.

• до C: $$10+3=13,$$ значит метка меняется на $$13$$;
• до E: $$10+10=20,$$ это больше $$19,$$ метка не меняется;
• до F: $$10+8=18,$$ значит $$F=18.$$

Итоговые кратчайшие расстояния от вершины A:

• до B — $$5$$;
• до C — $$13$$;
• до D — $$10$$;
• до E — $$19$$;
• до F — $$18$$.

Ответ

$$A \to B = 5,\quad A \to C = 13,\quad A \to D = 10,\quad A \to E = 19,\quad A \to F = 18.$$