Алгоритм Дейкстры (стр. 4 из 4)
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Четвертая итерация
Шаг 2.
; 
Шаг 3.
соответствует x3.Шаг 4. x3 получает постоянную пометку l(x3)=13+, p=x3.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Пятая итерация
Шаг 2.
; 
Шаг 3.
соответствует x8.Шаг 4. x8 получает постоянную пометку l(x8)=16+, p=x8.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Шестая итерация
Шаг 2.
; 
Шаг 3.
соответствует x7.Шаг 4. x7 получает постоянную пометку l(x7)=17+, p=x7.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Седьмая итерация
Шаг 2.
; 
; 
Шаг 3.
соответствует x10.Шаг 4. x10 получает постоянную пометку l(x10)=18+, p=x10.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Восьмая итерация
Шаг 2.
; 
Шаг 3.
соответствует x5.Шаг 4. x5 получает постоянную пометку l(x5)=19+, p=x5.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Девятая итерация
Шаг 2.
; 
Шаг 3. x9 получает постоянную пометку l(x9)=21+.
Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа
Алгоритм работает так:
Шаг 1.
.Первая итерация
Шаг 2.
; 
; 
Шаг 3.
соответствует x7.Шаг 4. x7 получает постоянную пометку l(x7)=6+, p=x7.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Вторая итерация
Шаг 2.
; 
Шаг 3.
соответствует x2.Шаг 4. x2 получает постоянную пометку l(x2)=7+, p=x2.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Третья итерация
Шаг 2.
; 
Шаг 3.
соответствует x4.Шаг 4. x4 получает постоянную пометку l(x4)=8+, p=x4.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Четвертая итерация
Шаг 2.
; 
; 
;Шаг 3.
соответствует x5.Шаг 4. x5 получает постоянную пометку l(x5)=16+, p=x5.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Пятая итерация
Шаг 2.
; 
; 
Шаг 3.
соответствует x8.Шаг 4. x8 получает постоянную пометку l(x8)=16+, p=x8.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Шестая итерация
Шаг 2.
; 
Шаг 3.
соответствует x3.Шаг 4. x3 получает постоянную пометку l(x3)=18+, p=x3.
Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.
Седьмая итерация
Шаг 2.
; 
Шаг 3. x6 получает постоянную пометку l(x6)=20+.
3. Алгоритмизация задачи
1) Вводим количество вершин неориентированного графа.
2) Если количество вершин больше 5, то переходим к пункту 3; иначе переходим к пункту 4.
3) Генератором случайных чисел произвольно задаются связи между вершинами в матрице смежностей, переходим к пункту 5.
4) Вводим связи между вершинами, исходя из следующего условия:
- если не существует пути длиной в одно ребро из одной вершины в другую, то ставим «100»,
- если существует путь между двумя вершинами, то ставим произвольное положительное ненулевое значение веса дуги.
Все введенные данные заносятся в матрицу смежностей.
5) Вводим номера вершин, путь между которыми нужно найти.
6) Задаем начальные значения длин путей равных 100 (в программе это обозначает бесконечность), а пометки всех вершин обнуляем.
7) Для начальной вершины в матрицу, хранящую пути (предшествующие вершины), заносим значение нуль, поскольку нет вершин предшествующих началу, значению пути присваиваем значение нуля, пометку на вершину устанавливаем в единицу.
8) Измененяем длины путей между вершинами «i» и начальной при условии, что рассматриваемая дуга не идет из вершины в саму себя и пометка этой вершины равна нулю, то тогда:
а) просматриваем длину пути в вершину «i» и сравниваем с длиной пути из начальной вершины «Nac»
б) получаем, что длина пути из вершины «s» меньше начального значения пути в вершину «i», то запоминаем в T[i] – ом элементе новую длину пути (меньшую) и H[i] – му присваиваем значение «s».
9) Присваиваем переменной ‘t» значение 100 (бесконечность), а переменной для хранения текущей вершины «k» присваиваем значение нуль.
10) Производим попытку уменьшить длину пути. Если вершина не помечена (ее пометка равна нулю), то если длина пути меньше значения «t» то значению «t» присваиваем текущее значение пути, а переменной для хранения текущей вершины «k» даем значение этой переменной.
11) Если переменная для хранения текущей вершины имеет значение нуля, то пути нет, переходим к пункту 14, иначе переходим к пункту 12.
12) Если переменная для хранения текущей вершины имеет значение конечной вершины, то путь найден, он кратчайший, переходим к пункту 14, иначе переходим к пункту 13.
13) Пометку на вершину, которую хранит переменная «k», изменяем на единицу и переходим к пункту 8.
14) Выводим на экран сообщение о длине пути между вершинами, если такой путь существует (т.е. путь имеет неотрицательную длину).
4 Экранная форма интерфейса и инструкция пользователя