Рассмотрите рисунок, кружками обозначены вершины графа, в кружки вписаны имена вершин

Задание 43. Рассмотрите рисунок. Кружками обозначены вершины графа; в кружки вписаны имена вершин. Вершины соединены линиями (ребрами графа); над ребрами обозначены их веса — длины пути. Рядом с каждой вершиной указана метка — длина кратчайшего пути в эту вершину из вершины А: для вершины А — это 0, для всех других вершин она пока неизвестна и обозначена знаком ∞ (бесконечность).

Найдите кратчайшее расстояние от вершины А до всех остальных вершин графа, действуя в соответствии с приведенным ниже алгоритмом Дейкстры.

1. Обведите вершину А, имеющую минимальную метку (0).
Укажите ее соседей — вершины, в которые идут ребра из вершины А: C, D, B

2. Установите очередность соседних с А вершин (по возрастанию длины пути между А и соседней вершиной):
1) первой по очереди идет вершина B(5), потому что длина пути между А и B является минимальной;
2) второй по очереди идет вершина D(10);
3) третьей по очереди идет вершина C(15).

3. В порядке установленной выше очередности измените метки для соседних с А вершин: вычислите сумму метки вершины А (обведенной вершины) и длины ребра, идущего из нее в очередную соседнюю вершину; если полученная сумма меньше текущей метки очередной вершины, то эту сумму запишите в качестве метки очередной вершины.
После просмотра всех соседей вершины А вычеркните ее из графа.

1) Через вершину B: A-D=14; A-E=19

2) Через вершину D: A-B=19; A-E=20; A-F=18; A-C=13

3) Через вершину C: A-F=22; A-D=18

4. Повторите действия 1-3 для оставшихся вершин, каждый раз выбирая из них вершину, имеющую минимальную метку.

Кратчайшее расстояние

из A в B равно 5

из A в C равно 13

из A в D равно 10

из A в E равно 19

из A в F равно 18