Рассмотрим вариант решения задания из учебника Босова, Аквилянов 9 класс, Просвещение: 3.43. Рассмотрите рисунок. Кружками обозначены вер-шины графа; в кружки вписаны имена вершин. Вершины соединены линиями (ребрами графа); над ребрами обозначены их веса — длины пути. Рядом с каждой вершиной указана метка — длина кратчайшего пути в эту вершину из вершины А: для вершины А — это 0, для всех других вершин она пока неизвестна и обозначена знаком бесконечность. Найдите кратчайшее расстояние от вершины А до всех остальных вершин графа, действуя в соответствии с приведенным ниже алгоритмом Дейкстры. 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.
