1.2. Пример решения задачи методом Дейкстры

Дан граф:

Найти кратчайший маршрут из в.

Введем в рассмотрение матрицу :— матрицас элементами

—длина ребра, соединяющего вершины и:

.

0-й шаг (инициализация алгоритма).

, ,

, ,.

1-й шаг.

.

Пересчет меток :

;

.

Из всех временных меток выбирается минимальная:

.

, ,.

, .

2-й шаг.

.

Пересчет меток :

метка постоянная, поэтому она не пересчитывается;

;

;

.

Из всех временных меток выбирается минимальная:

.

, ,.

, .

3-й шаг.

.

Пересчет меток :

метки ипостоянные, поэтому они не пересчитываются;

;

.

Из всех временных меток выбирается минимальная:

.

, ,.

, .

4-й шаг.

.

Пересчет меток :

метки ипостоянные, поэтому они не пересчитываются;

.

Метка принимается за окончательную, причем значение метки равное 7 — вес минимального маршрута изв.

, .

Определяем последовательность вершин в минимальном маршруте.

.

,

,

.

Вершине в минимальном маршруте предшествует вершина.

.

,

,

,

.

Вершине в минимальном маршруте предшествуют вершиныили. Поскольку вершинаначальная, то путьявляется минимальным.

.

,

,

,

.

Таким образом, путь также является минимальным.