Порядок выполнения работы. Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных

Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – ребра графа. В кружках обозначены номера вершин, над ребрами обозначена их вес – (или длина пути).

Рядом с каждой вершиной обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

7<¥, поэтому метка ¥ при вершине 2 заменяется меткой 7,

9<¥, поэтому метка ¥ при вершине 3 заменяется меткой 9,

14<¥, поэтому метка ¥ при вершине 6 заменяется меткой 14,

вершина 1 вычеркивается из числа посещенных вершин.

7+10=17>9, поэтому метка 9 при вершине 3 остается;

7+15=22<¥, поэтому метка ¥ при вершине 4 заменяется меткой 22;

вершина 2 вычеркивается из числа посещенных вершин.

9+11=20<22, поэтому метка 22 при вершине 4 заменяется меткой 20;

9+2=11<14, поэтому метка 14 при вершине 6 заменяется меткой 11;

вершина 3 вычеркивается из числа посещенных вершин.

11+9=20<¥, поэтому метка ¥ при вершине 5 заменяется меткой 20;

вершина 6 вычеркивается из числа посещенных вершин.

20+6=26>20, поэтому метка 20 при вершине 5 остается;

вершина 4 вычеркивается из числа посещенных вершин.

У вершины 5 не посещенных смежных вершин нет, поэтому вершина 5 также вычеркивается из числа не посещенных вершин.

Алгоритм заканчивает работу, так как нельзя больше обработать ни одной вершины. Кратчайшие пути – это последние метки при вершинах.

Самостоятельно задание. Задайте некоторый граф с весами в виде матрицы смежности. Постройте последовательное выполнение алгоритма Дейкстры на диаграммах графа.