Алгоритм Дейкстры: поиск кратчайшего пути в графах

Алгоритм Дейкстры, названный в честь его создателя Эдсгера Дейкстры, является фундаментальным методом в области теории графов и вычислительной математики, предназначенным для нахождения кратчайших путей в графах. Этот алгоритм широко применяется в различных областях, включая сетевые маршрутизации, географические информационные системы (ГИС), а также в задачах оптимизации и логистики.

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

Алгоритм Дейкстры обладает несколькими ключевыми преимуществами.

Эффективность. Алгоритм способен решать задачи поиска кратчайшего пути в графах с большим числом вершин и ребер за разумное время.

Простота реализации. Структура алгоритма относительно проста и понятна, что делает его удобным для реализации на различных языках программирования.

Обобщаемость. Алгоритм может быть адаптирован для решения различных задач, требующих учета минимальных затрат.

Благодаря этим преимуществам алгоритм Дейкстры находит широкое применение в различных сферах.

Маршрутизация в сетях. Оптимизация путей передачи данных в компьютерных сетях.

Навигационные системы. Определение кратчайших маршрутов на картах.

Логистика и транспорт. Оптимизация маршрутов доставки и перемещения транспорта.

Анализ социальных сетей. Изучение кратчайших связей между пользователями.

Рассмотрим два основных подхода к описанию и применению этого алгоритма: итеративный метод и табличный способ.

Итеративный метод. В этом методе алгоритм Дейкстры реализуется путем пошагового итеративного обновления расстояний до вершин. Этот метод подробно объясняет каждый шаг алгоритма, включая выбор вершины с наименьшим текущим расстоянием, обновление расстояний до соседних вершин и повторение этого процесса до тех пор, пока не будут найдены кратчайшие пути до всех вершин.

Табличный способ. Этот метод представляет выполнение алгоритма Дейкстры в виде таблицы, где каждая строка таблицы соответствует одной итерации алгоритма. В таблице указаны текущие расстояния до каждой вершины и предшествующие вершины на пути, что позволяет наглядно проследить процесс нахождения кратчайших путей. Этот подход структурирован и удобен для визуализации прогресса алгоритма.

Оба метода полезны для понимания и применения алгоритма Дейкстры, обеспечивая различные уровни детализации и визуализации процесса.

Задача 1.5.1. Найти кратчайший путь, используя алгоритм Дейкстры от вершины A до вершины K.

Рисунок 1.5.1 – Взвешенный граф - Теория графов polenet.ru — Рисунок 1.5.1 – Взвешенный граф

Решение. Найдем кратчайший путь от вершины A до вершины K, используя алгоритм Дейкстры, двумя способами.

Итеративный метод

В данном подходе подробно объясняется, как работает алгоритм Дейкстры. Его реализация включает в себя несколько этапов.

— Инициализация. Устанавливаются начальные расстояния до всех вершин, начальная вершина получает расстояние 0 (так как расстояния до самой себя равно нулю), а остальные — бесконечность (так как на начальном этапе, когда мы ещё не начали обход графа, расстояния до всех вершин графа неизвестны).

— Выбор текущей вершины. Выбирается вершина с минимальным известным расстоянием, которая еще не обработана.

— Обновление расстояний. Для всех соседних вершин текущей вершины проверяются и при необходимости обновляются кратчайшие расстояния.

— Повторение. Шаги повторяются до тех пор, пока не будут обработаны все вершины или не будет найден кратчайший путь до конечной вершины.

Шаг 1. Инициализация

Создаем множество $S$ посещённых вершин и изначально устанавливаем его пустым: $S = \varnothing$ .

Инициализируем массив расстояний $d$ для всех вершин:

— $d[A] = 0$ (расстояние до самой себя);

— $d[v] = \infty$ для всех остальных вершин, где $v$ принимает значения множества вершин графа.

Таким образом, массив расстояний до вершин будет выглядеть следующим образом:

$d = \{A: 0; B: \infty; C: \infty; D: \infty; E: \infty;$ $F: \infty; G: \infty; H: \infty; I: \infty; J: \infty; K: \infty\},$

что означает $d[A] = 0$ ; $d[B] = \infty$ ; $d[C] = \infty$ ; $d[D] = \infty$ ; $d[E] = \infty$ ; $d[F] = \infty$ ; $d[G] = \infty$ ; $d[H] = \infty$ ; $d[I] = \infty$ ; $d[J] = \infty$ ; $d[K] = \infty$ .

Создаем массив предшественников $p$ для отслеживания пути:

— $p[v] = \text{null}$ для всех вершин, т. е.

$p = \{A: \text{null}, B: \text{null}, C: \text{null}, D: \text{null}, E: \text{null},$ $F: \text{null}, G: \text{null}, H: \text{null}, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Под термином «предшественник» мы будем понимать предыдущую вершину.

Запись $p[v] = \text{null}$ для всех вершин означает, что на начальном этапе алгоритма Дейкстры мы устанавливаем значение предшественника для каждой вершины равным «null» (null — это стандартный термин в программировании, обозначающий отсутствие значения или неопределённое состояние). Она означает, что на начальном этапе для каждой вершины предшественник не определён, то есть мы ещё не знаем, из какой вершины мы придём в данную вершину при построении кратчайшего пути. Это необходимо для того, чтобы в дальнейшем, по мере выполнения алгоритма, обновлять значения предшественников, когда мы находим более короткие пути к вершинам.

Предшественник вершины $v$ в нашем алгоритме указывает на вершину, из которой мы пришли в вершину $v$ по кратчайшему пути; массив предшественников $p$ хранит информацию о том, из какой вершины мы пришли в данную вершину при движении по кратчайшему пути. Это позволяет нам в конце работы алгоритма восстановить путь от начальной вершины до любой другой вершины, следуя от конечной точки к начальной через предшественников.

Инициализация предшественников.

На начальном этапе, когда мы ещё не начали обход графа, для всех вершин предшественники неизвестны, поэтому их значения устанавливаются в $\text{null}$ (или $\text{None}$ в Python). Это означает, что на начальном этапе ни для одной вершины нет известного предшественника.

В массиве предшественников $p$ хранится «маршрут» для каждой вершины.

Как только алгоритм Дейкстры приступает к работе, он начинает обновлять значения предшественников, когда находит более короткие пути. Например, если при обработке вершины $A$ он обнаруживает, что можно прийти в вершину $B$ через вершину $A$ с определённым весом, то происходит обновление $p[B] = A$ .

Таким образом, по мере выполнения алгоритма, массив предшественников начинает заполняться конкретными значениями вершин, из которых мы приходим.

Для восстановления кратчайшего пути из стартовой вершины до какой-либо другой необходимо проследовать по массиву $p$ от конечной вершины к начальной.

Шаг 2. Основной цикл алгоритма

Алгоритм выполняется, пока не будут посещены все вершины. На каждом шаге выбираем вершину с наименьшим известным расстоянием, обновляем расстояния до её соседей и отмечаем вершину как посещённую.

Итерация 1: обработка вершины $A$ .

Выбираем вершину с наименьшим расстоянием: $A\ (d[A] = 0)$ .

Обновляем расстояния до соседей $A$ (смежных ей вершин):

— $B: d[B] = \min(\infty, 0 + 2) = \min(\infty, 2) = 2$ , так как $2 < \infty$ ;

— $C: d[C] = \min(\infty, 0 + 4) = 4$ , так как $4 < \infty$ ;

— $D: d[D] = \min(\infty, 0 + 3) = 3$ , так как $3 < \infty$ .

Функция $\min(a, b)$ сравнивает значения входящих переменных и возвращает наименьшее.

Во множество посещенных вершин $S$ добавляем $A$ , и таким образом имеем $S = \{A\}$ .

Предшествующей вершиной для вершин $B$ , $C$ и $D$ является $A$ : $p[B] = A$ , $p[C] = A$ , $p[D] = A$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: \infty, F: \infty, G: \infty, H: \infty, I: \infty, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: \text{null}, F: \text{null},$ $G: \text{null}, H: \text{null}, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Итерация 2: обработка вершины] $B$ .

Выбираем вершину с наименьшим расстоянием: $B\ (d[B] = 2)$ .

Обновляем расстояния до соседей $B$ :

— $A$ : уже посещена;

— $H: d[H] = \min(\infty, 2 + 9) = 11$ ; $p[H] = B$ .

$S = \{A, B\}$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: \infty, F: \infty, G: \infty, H: 11, I: \infty, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: \text{null}, F: \text{null},$ $G: \text{null}, H: B, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Итерация 3: обработка вершины] $D$ .

Выбираем вершину с наименьшим расстоянием: $D\ (d[D] = 3)$ .

Обновляем расстояния до соседей $D$ :

— $A$ : уже посещена;

— $E: d[E] = \min(\infty, 3 + 7) = 10$ ; $p[E] = D$ ;

— $F: d[F] = \min(\infty, 3 + 1) = 4$ ; $p[F] = D$ .

$S = \{A, B, D\}$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: 10, F: 4, G: \infty, H: 11, I: \infty, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: D, F: D, G: \text{null}, H: B, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Итерация 4: обработка вершины $C$ .

Выбираем вершину с наименьшим расстоянием: $C\ (d[C] = 4)$ .

Обновляем расстояния до соседей $C$ :

— $A$ : уже посещена;

— $F: d[F] = \min(4, 4 + 4) = 4$ ; $p[F] = D$ ;

— $I: d[I] = \min(\infty, 4 + 7) = 11$ ; $p[I] = C$ .

$S = \{A, B, D, C\}$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: 10, F: 4, G: \infty, H: 11, I: 11, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: D, F: D, G: \text{null},$ $H: B, I: C, J: \text{null}, K: \text{null}\}.$

Итерация 5: обработка вершины $F$ .

Выбираем вершину с наименьшим расстоянием: $F\ (d[F] = 4)$ .

Обновляем расстояния до соседей $F$ :

— $D$ : уже посещена;

— $G: d[G] = \min(\infty, 4 + 2) = 6$ ; $p[G] = F$ ;

— $C$ : уже посещена;

— $I: d[I] = \min(11, 4 + 8) = 11$ ; не обновляется.

$S = \{A, B, D, C, F\}$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: 10, F: 4, G: 6, H: 11, I: 11, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: D, F: D, G: F, H: B, I: C, J: \text{null}, K: \text{null}\}.$

Итерация 6: обработка вершины $G$ .

Выбираем вершину с наименьшим расстоянием: $G\ (d[G] = 6)$ .

Обновляем расстояния до соседей $G$ :

— $E: d[E] = \min(10, 6 + 6) = 10$ , не обновляется;

— $F$ : уже посещена;

— $I: d[I] = \min(11, 6 + 3) = 9$ ; $p[I] = G$ ;

— $J: d[J] = \min(\infty, 6 + 3) = 9$ ; $p[J] = G$ .

$S = \{A, B, D, C, F, G\}$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: 10, F: 4, G: 6, H: 11, I: 9, J: 9, K: \infty\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: D, F: D, G: F, H: B, I: G, J: G, K: \text{null}\}.$

Итерация 7: обработка вершины $I$ .

Выбираем вершину с наименьшим расстоянием: $I\ (d[I] = 9)$ .

Обновляем расстояния до соседей $I$ :

— $C, F, G$ : посещены;

— $H: d[H] = \min(11, 9 + 4) = 11$ , не обновляется;

— $K: d[K] = \min(\infty, 9 + 2) = 11$ ; $p[K] = I$ .

$S = \{A, B, D, C, F, G, I\}$ .

Обновлённые значения массивов $d$ и $p$ :

$d = \{A: 0, B: 2, C: 4, D: 3, E: 10, F: 4, G: 6, H: 11, I: 9, J: 9, K: 11\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: D, F: D, G: F, H: B, I: G, J: G, K: I\}.$

Итерация 8: обработка вершины $J$ .

Выбираем вершину с наименьшим расстоянием: $J\ (d[J] = 9)$ .

Обновляем расстояния до соседей $J$ :

— $G$ : посещена;

— $K: d[K] = \min(11, 9 + 6) = 11$ ; не обновляется.

$S = \{A, B, D, C, F, G, I, J\}$ .

Значения массивов $d$ и $p$ остаются прежними:

$d = \{A: 0, B: 2, C: 4, D: 3, E: 10, F: 4, G: 6, H: 11, I: 9, J: 9, K: 11\};$

$p = \{A: \text{null}, B: A, C: A, D: A, E: D, F: D, G: F, H: B, I: G, J: G, K: I\}.$

Итерация 9: обработка вершины $E$ .

Выбираем вершину с наименьшим расстоянием: $E\ (d[E] = 10)$ .

Обновляем расстояния до соседей $E$ :

— $D, G$ : посещены;

$E$ не обновляет никаких значений, так как все её соседи уже обработаны.

$S = \{A, B, D, C, F, G, I, J, E\}$ .

Значения массивов $d$ и $p$ остаются прежними.

Итерация 10: обработка вершины $H$ .

Выбираем вершину с наименьшим расстоянием: $H\ (d[H] = 11)$ .

Обновляем расстояния до соседей $H$ :

— $B, I$ : посещены;

$H$ не обновляет никаких значений, так как все её соседи уже обработаны.

$S = \{A, B, D, C, F, G, I, J, E, H\}$ .

Значения массивов $d$ и $p$ остаются прежними.

Все вершины посещены.

Теперь, когда все вершины посещены и массивы $d$ и $p$ заполнены, можем восстановить кратчайший путь от $A$ до $K$ по массиву предшественников $p$ и узнать длину пути из массива $d$ .

Восстановление кратчайшего пути.

Начинаем с вершины $K$ .

Предшественником вершины $K$ является вершина $I$ .

Предшественник $I$ — $G$ .

Предшественник $G$ — $F$ .

Предшественник $F$ — $D$ .

Предшественник $D$ — $A$ .

Итак, кратчайший путь: $A \rightarrow D \rightarrow F \rightarrow G \rightarrow I \rightarrow K$ .

Длина кратчайшего пути: $A \rightarrow K$ равна $d[K] = 11$ .

Таким образом, мы нашли кратчайший путь и его длину, используя итеративный метод алгоритма Дейкстры.

Табличный способ

Согласно данному способу, весь алгоритм определяется следующими шагами.

Инициализация таблицы.

— Создается таблица, где строки соответствуют шагам алгоритма, а столбцы — вершинам графа.

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

Выбор текущей вершины.

— В каждой строке таблицы указывается выбранная вершина, для которой будет производиться обновление расстояний. На первом шаге это стартовая вершина.

Обновление расстояний.

— Для выбранной вершины обновляются расстояния до всех соседних вершин. Если через выбранную вершину можно пройти в соседнюю вершину с меньшим суммарным расстоянием, чем ранее записанное в таблице, то это расстояние обновляется.

— В таблице фиксируются обновленные значения расстояний.

— В таблице фиксируется общая длина пути от начальной вершины до выбранной вершины (числовая метка).

Маркировка выбранных вершин.

— В таблице отмечается, что выбранная вершина больше не будет рассматриваться (она выбрана).

Повторение шагов.

— Выбирается следующая вершина с наименьшим текущим расстоянием среди оставшихся невыбранных вершин.

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

Завершение алгоритма.

— Процесс продолжается до тех пор, пока все вершины не будут выбраны или пока не будет достигнута конечная вершина (если она задана).

— В итоге таблица будет содержать кратчайшие расстояния от начальной вершины до всех других вершин и последовательность шагов для их вычисления.

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

Реализация алгоритма

Шаг 0. Устанавливаются начальные расстояния до всех вершин, начальная вершина получает расстояние 0 (расстояние от самой себя равно нулю), а остальные — бесконечность ( $\infty$ ), так как на данном этапе, когда мы ещё не начали обход графа, расстояния до всех вершин графа неизвестны, мы не знаем для них кратчайший путь от начальной вершины. Для удобства визуального восприятия все изменения также будем фиксировать на графе. Числовые метки над вершинами графа будут обозначать кратчайший путь до данной вершины от начальной.

Рисунок 1.5.2 – Алгоритм Дейкстры, шаг 0 - Теория графов polenet.ru — Рисунок 1.5.2 – Алгоритм Дейкстры, шаг 0

Шаг 1. Определяем расстояния от начальной вершины A до всех остальных вершин.

Записываем в таблицу расстояния до тех вершин, с которыми она соединена (смежна, соседние вершины):

B — расстояние (длина ребра АВ, вес АВ) равно 2, обновлено, так как $2 < \infty$ ;

С — 4 (вес АС), обновлено, так как $4 < \infty$ ;

D — 3 (вес AD), обновлено, так как $3 < \infty$ .

Определяем расстояние до соседних вершин, сравниваем расстояния и, если необходимо, обновляем числовые метки. На данном этапе, мы определили расстояния до соседних вершин, сравнили значения и обновили числовые метки, так как новые расстояния оказались меньше прежних.

Расстояния до остальных вершин на данном этапе алгоритма остаются неизвестными, так как вершина А напрямую с ними не взаимодействует (не соединена), поэтому заполняем ячейки значением $\infty$ .

Таблица 1.5.1 — Алгоритм Дейкстры, шаг 1

Выбираем вершину с наименьшим расстоянием от исходной — это вершина В, расстояние до которой 2. Записываем ее в столбец выбранных вершин и фиксируем расстояние до нее в первый столбец.

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.3 – Алгоритм Дейкстры, шаг 1 - Теория графов polenet.ru — Рисунок 1.5.3 – Алгоритм Дейкстры, шаг 1

Шаг 2. Выбрана вершина В. Обновляем расстояния до соседних вершин.

Вершина В соединена с вершинами:

— А: так как А уже выбрана, то ее не рассматриваем;

— Н: 2 (числовая метка В) + 9 (вес ребра ВН) = 11. Обновляем, так как $11 < \infty$ .

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

Значения расстояний до вершин С и D переписываем с предыдущего шага, так как вершина В с ними не взаимодействует, следовательно расстояния до них от начальной вершины не обновляет.

Таблица 1.5.2 — Алгоритм Дейкстры, шаг 2

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.4 – Алгоритм Дейкстры, шаг 2 - Теория графов polenet.ru — Рисунок 1.5.4 – Алгоритм Дейкстры, шаг 2

Шаг 3. Выбрана вершина D, так как имеет минимальное значение расстояния, равное 3. Обновляем расстояния до соседних вершин.

Вершина D соединена с вершинами:

— А: так как А уже выбрана, то ее не рассматриваем;

— Е: 3 (числовая метка D) + 7 (вес ребра DЕ) = 10. Обновляем, так как $10 < \infty$ ;

— F: 3 (числовая метка D) + 1 (вес ребра DF) = 4. Обновляем, так как $4 < \infty$ .

Значения расстояний до вершин С и H переписываем с предыдущего шага, так как вершина D с ними не взаимодействует, следовательно расстояния до них от начальной вершины не обновляет.

Для удобства визуального восприятия заменим в таблице знак бесконечности на прочерк.

Таблица 1.5.3 — Алгоритм Дейкстры, шаг 3

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.5 – Алгоритм Дейкстры, шаг 3 - Теория графов polenet.ru — Рисунок 1.5.5 – Алгоритм Дейкстры, шаг 3

Шаг 4. Выбрана вершина С, так как имеет минимальное значение расстояния, равное 4. Мы также можем выбрать вершину F, имеющую такое же расстояние. Порядок выбора вершин с одинаковым текущим кратчайшим расстоянием, не влияет на корректность алгоритма и на конечный результат. Поэтому можно выбрать любую вершину. Мы будем придерживаться лексикографического порядка (обрабатывать вершины согласно порядку следования по алфавиту).

Обновляем расстояния до соседних вершин.

Вершина С соединена с вершинами:

— А: так как А уже выбрана, то ее не рассматриваем;

— F: 4 (числовая метка C) + 4 (вес ребра CF) = 8. Не обновляем, так как $4 < 8$ , предыдущая метка 4 меньше получившейся 8, т. е. попасть в вершину F можно за более короткое расстояние.

— I: 4 (числовая метка C) + 7 (вес ребра CI) = 11. Обновляем, так как $11 < \infty$ .

Значения расстояний до вершин Е и H переписываем с предыдущего шага, так как вершина C с ними не взаимодействует, следовательно расстояния до них от начальной вершины не обновляет.

Таблица 1.5.4 — Алгоритм Дейкстры, шаг 4

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.6 – Алгоритм Дейкстры, шаг 4 - Теория графов polenet.ru — Рисунок 1.5.6 – Алгоритм Дейкстры, шаг 4

Шаг 5. Выбрана вершина F, так как имеет минимальное значение расстояния, равное 4.

Обновляем расстояния до соседних вершин.

Вершина F соединена с вершинами:

— D, C: уже выбраны, не рассматриваем;

— G: 4 (числовая метка F) + 2 (вес ребра FG) = 6, обновляем, так как $6 < \infty$ ;

— I: 4 (числовая метка F) + 8 (вес ребра FI) = 12, не обновляем, так как $11 < 12$ .

Значения расстояний до вершин Е и H переписываем с предыдущего шага, так как вершина F с ними не взаимодействует, следовательно расстояния до них от начальной вершины не обновляет.

Таблица 1.5.5 — Алгоритм Дейкстры, шаг 5

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.7 – Алгоритм Дейкстры, шаг 5 - Теория графов polenet.ru — Рисунок 1.5.7 – Алгоритм Дейкстры, шаг 5

Шаг 6. Выбрана вершина G, так как имеет минимальное значение расстояния, равное 6.

Обновляем расстояния до соседних вершин.

Вершина G соединена с вершинами:

— F: уже выбрана, не рассматриваем;

— Е: 6 (числовая метка G) + 6 (вес ребра GE) = 12, не обновляем, так как $10 < 12$ .

— J: 6 (числовая метка G) + 3 (вес ребра GJ) = 9, обновляем, так как $9 < \infty$ ;

— I: 6 (числовая метка G) + 3 (вес ребра GI) = 9, обновляем, так как $9 < 11$ .

Значение расстояния до вершины H переписываем с предыдущего шага, так как вершина G с ней не взаимодействует, следовательно расстояние до нее от начальной вершины не обновляет.

Таблица 1.5.6 — Алгоритм Дейкстры, шаг 6

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.8 – Алгоритм Дейкстры, шаг 6 - Теория графов polenet.ru — Рисунок 1.5.8 – Алгоритм Дейкстры, шаг 6

Шаг 7. Выбрана вершина I, так как имеет минимальное значение расстояния, равное 9.

Обновляем расстояния до соседних вершин.

Вершина I соединена с вершинами:

— C, F, G: посещены;

— H: 9 (числовая метка I) + 4 (вес ребра IH) = 13, не обновляем, так как $11 < 13$ ;

— K: 9 (числовая метка I) + 2 (вес ребра IK) = 11, обновляем, так как $11 < \infty$ .

Значения расстояний до вершин Е и J переписываем с предыдущего шага, так как вершина I с ними не взаимодействует, следовательно расстояния до них от начальной вершины не обновляет.

Таблица 1.5.7 — Алгоритм Дейкстры, шаг 7

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.9 – Алгоритм Дейкстры, шаг 7 - Теория графов polenet.ru — Рисунок 1.5.9 – Алгоритм Дейкстры, шаг 7

Шаг 8. Выбрана вершина J, так как имеет минимальное значение расстояния, равное 9.

Обновляем расстояния до соседних вершин.

Вершина J соединена с вершинами:

— G: посещена;

— K: 9 (числовая метка J) + 6 (вес ребра JK) = 15, не обновляем, так как $11 < 15$ .

Значения расстояний до вершин Е и H переписываем с предыдущего шага, так как вершина J с ними не взаимодействует, следовательно расстояния до них от начальной вершины не обновляет.

Таблица 1.5.8 — Алгоритм Дейкстры, шаг 8

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.10 – Алгоритм Дейкстры, шаг 8 - Теория графов polenet.ru — Рисунок 1.5.10 – Алгоритм Дейкстры, шаг 8

Шаг 9. Выбрана вершина E, так как имеет минимальное значение расстояния, равное 10.

Обновляем расстояния до соседних вершин.

Вершина E соединена с вершинами:

— D, G: уже выбраны, не рассматриваем, следовательно вершина E не обновляет никаких значений.

Значение расстояния до вершины H переписываем с предыдущего шага, так как вершина E с ней не взаимодействует, следовательно расстояние до нее от начальной вершины не обновляет.

Таблица 1.5.9 — Алгоритм Дейкстры, шаг 9

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.11 – Алгоритм Дейкстры, шаг 9 - Теория графов polenet.ru — Рисунок 1.5.11 – Алгоритм Дейкстры, шаг 9

Шаг 10. Выбрана вершина H, так как имеет минимальное значение расстояния, равное 11.

Обновляем расстояния до соседних вершин.

Вершина H соединена с вершинами:

— B, I: уже выбраны, не рассматриваем, следовательно вершина H не обновляет никаких значений.

Таблица 1.5.10 — Алгоритм Дейкстры, шаг 10

Обновляем метки расстояний на графе и закрашиваем обработанные вершины.

Рисунок 1.5.12 – Алгоритм Дейкстры, шаг 10 - Теория графов polenet.ru — Рисунок 1.5.12 – Алгоритм Дейкстры, шаг 10

Таким образом, мы проработали все вершины и определили все возможные пути до вершины К, теперь найдем кратчайший путь. Анализируем столбец, соответствующий конечной вершине К, сверху вниз и фиксируем первое появление минимального значения — это 11, которое соответствует строке вершины I; далее переходим к столбцу, который соответствует вершине I, снова просматриваем его содержимое и первое появление минимального значения соответствует строке вершины G, переходим к одноименному столбцу и повторяем процесс снова. Таким образом, следующая вершина F, далее D и A. Кратчайший путь от А до К: A, D, F, G, I, K и его длина равна 11 (отображен в ячейке таблицы с номером строки I, номером столбца K и меткой вершины К на графе).

Ответ. Расстояние между вершинами — 11; кратчайший путь, найденный согласно алгоритму Дейкстры: A, D, F, G, I, K.

Рисунок 1.5.13 – Кратчайший путь от А до К - Теория графов polenet.ru — Рисунок 1.5.13 – Кратчайший путь от А до К

Оба подхода эффективны для понимания и визуализации работы алгоритма Дейкстры, обеспечивая ясное представление о процессе поиска кратчайшего пути в графе.

Замечания

В алгоритме Дейкстры, если у вас есть две вершины с одинаковым текущим кратчайшим расстоянием, то выбор, какую из них обрабатывать первой, не влияет на корректность алгоритма и на конечный результат (т. е. на найденные кратчайшие пути). Однако, этот выбор может повлиять на порядок обработки вершин и, следовательно, на промежуточные состояния данных.

Распространены два подхода. 1. Произвольный выбор. Обычно выбирают произвольно одну из вершин. Например, выбирают ту, которая появилась первой в наборе необработанных вершин. 2. Лексикографический порядок. В некоторых реализациях предпочитают использовать порядок вершин в графе (например, по алфавиту имен вершин или по их индексам), чтобы обеспечить определенный и предсказуемый порядок обработки.

Пример. Произвольный выбор. Пусть у нас есть две вершины $A$ и $B$ с одинаковым текущим кратчайшим расстоянием равным 10. Мы можем выбрать любую из них первой, например сначала выбрать $B$ , а затем $A$ .

Лексикографический порядок. Если мы выбираем по лексикографическому порядку (например, по алфавиту), то первой выбираем $A$ , так как $A$ идет перед $B$ в алфавитном порядке.

Выбор, какую вершину обрабатывать первой при одинаковом расстоянии, может быть реализован по-разному. Важно понимать, что:

— корректность алгоритма не нарушается, алгоритм Дейкстры гарантированно найдет кратчайшие пути независимо от порядка обработки вершин с одинаковым расстоянием;

— для обеспечения предсказуемого поведения и удобства отладки часто используется лексикографический порядок или порядок добавления вершин в графе.

Таким образом, можно выбирать вершину произвольно или использовать лексикографический порядок, что в конечном итоге зависит от конкретной реализации алгоритма и требований к программе.

В алгоритме Дейкстры обрабатывать конечную вершину не обязательно, если вы достигли её и нашли кратчайший путь. Как только вы добавили конечную вершину (в данном случае вершину $H$ ) во множество $S$ (обработанных вершин) и обновили расстояния до всех её соседей, можно прекратить выполнение алгоритма.

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

Таким образом, формально обрабатывать конечную вершину необходимо для корректного завершения алгоритма, особенно если вам нужно знать кратчайшие пути до всех вершин. Но если вы ищете только путь до конкретной конечной вершины, можно остановиться, как только путь до неё будет найден.

Задача 1.5.2. Найти кратчайший путь, используя алгоритм Дейкстры от вершины E до вершины H.

Рисунок 1.5.14 – Взвешенный граф - Теория графов polenet.ru — Рисунок 1.5.14 – Взвешенный граф

Решение.

Итеративный метод

Шаги выполнения алгоритма Дейкстры для поиска кратчайшего пути от $E$ до $H$ .

Исходные данные.

— Вершины и ребра с весами:

— $A$ соединена с $B$ (вес 4), $C$ (вес 2), $D$ (вес 1);

— $B$ соединена с $A$ (вес 4) и $H$ (вес 9);

— $C$ соединена с $A$ (вес 2), $F$ (вес 4), $I$ (вес 7);

— $D$ соединена с $A$ (вес 1), $F$ (вес 1), $E$ (вес 7);

— $E$ соединена с $D$ (вес 7) и $G$ (вес 6);

— $F$ соединена с $D$ (вес 1), $G$ (вес 2), $I$ (вес 8), $C$ (вес 4);

— $G$ соединена с $F$ (вес 2), $E$ (вес 6), $J$ (вес 3), $I$ (вес 7);

— $H$ соединена с $B$ (вес 9) и $I$ (вес 4);

— $I$ соединена с $C$ (вес 7), $F$ (вес 8), $G$ (вес 7), $H$ (вес 4), $K$ (вес 2);

— $J$ соединена с $G$ (вес 3), $K$ (вес 1);

— $K$ соединена с $I$ (вес 2), $J$ (вес 1).

Инициализация.

— Расстояния:

$d = \{A: \infty, B: \infty, C: \infty, D: \infty, E: 0, F: \infty, G: \infty, H: \infty, I: \infty, J: \infty, K: \infty\}.$

— Предшественники:

$p = \{A: \text{null}, B: \text{null}, C: \text{null}, D: \text{null}, E: \text{null}, F: \text{null}, G: \text{null}, H: \text{null}, I: \text{null}, J: \text{null}, K: \text{null}\}.$

— Создаем множество $S$ посещённых вершин и изначально устанавливаем его пустым: $S = \varnothing$ .

Шаги выполнения.

Обработка вершины $E$ .

Взаимодействие с обработанными вершинами не рассматриваем.

— $E$ соединена с $D$ (вес 7) и $G$ (вес 6):

— $d[D] = 7$ , $p[D] = E$ ;

— $d[G] = 6$ , $p[G] = E$ .

— Обновлённые значения:

$d = \{A: \infty, B: \infty, C: \infty, D: 7, E: 0, F: \infty, G: 6, H: \infty, I: \infty, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: \text{null}, C: \text{null}, D: E, E: \text{null}, F: \text{null}, G: E, H: \text{null}, I: \text{null}, J: \text{null}, K: \text{null}\};$

— $S = \{E\}$ .

Обработка вершины $G$ .

— $G$ соединена с $F$ (вес 2), $J$ (вес 3), $I$ (вес 7):

— $d[F] = 8$ , $p[F] = G$ ;

— $d[J] = 9$ , $p[J] = G$ ;

— $d[I] = 13$ , $p[I] = G$ .

— Обновлённые значения:

$d = \{A: \infty, B: \infty, C: \infty, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 13, J: 9, K: \infty\};$

$p = \{A: \text{null}, B: \text{null}, C: \text{null}, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: G, J: G, K: \text{null}\};$

— $S = \{E, G\}$ .

Обработка вершины $D$ .

— $D$ соединена с $A$ (вес 1) и $F$ (вес 1):

— $d[A] = 8$ , $p[A] = D$ (обновление: $7 + 1 < \infty$ );

— $d[F] = 8$ (не обновляется, так как $7 + 1 = 8$ ).

— Обновлённые значения:

$d = \{A: 8, B: \infty, C: \infty, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 13, J: 9, K: \infty\};$

$p = \{A: D, B: \text{null}, C: \text{null}, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: G, J: G, K: \text{null}\};$

— $S = \{E, G, D\}$ .

Обработка вершины $A$ .

— $A$ соединена с $B$ (вес 4), $C$ (вес 2):

— $d[B] = 12$ , $p[B] = A$ (обновление: $8 + 4 < \infty$ );

— $d[C] = 10$ , $p[C] = A$ (обновление: $8 + 2 < \infty$ ).

— Обновлённые значения:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 13, J: 9, K: \infty\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: G, J: G, K: \text{null}\};$

— $S = \{E, G, D, A\}$ .

Обработка вершины $F$ .

— $F$ соединена с $C$ (вес 4), $I$ (вес 8):

— $d[C] = 10$ (не обновляется, так как $8 + 4 = 12 > 10$ );

— $d[I] = 16$ (не обновляется, так как $8 + 8 = 16 > 13$ ).

— Значения остаются прежними:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 13, J: 9, K: \infty\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: G, J: G, K: \text{null}\};$

— $S = \{E, G, D, A, F\}$ .

Обработка вершины $J$ .

— $J$ соединена с $K$ (вес 1):

— $d[K] = 10$ , $p[K] = J$ (обновление: $9 + 1 < \infty$ ).

— Обновлённые значения:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 13, J: 9, K: 10\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: G, J: G, K: J\};$

— $S = \{E, G, D, A, F, J\}$ .

Обработка вершины $C$ .

— $C$ соединена с $F$ (вес 4) и $I$ (вес 7):

— $d[F] = 8$ (не обновляется, так как $10 + 4 = 14 > 8$ );

— $d[I] = 13$ (не обновляется, так как $10 + 7 = 17 > 13$ ).

— Значения остаются прежними:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 13, J: 9, K: 10\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: G, J: G, K: J\};$

— $S = \{E, G, D, A, F, J, C\}$ .

Обработка вершины $K$ .

— $K$ соединена с $I$ (вес 2):

— $d[I] = 12$ , $p[I] = K$ (обновление: $10 + 2 < 13$ ).

— Обновлённые значения:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: \infty, I: 12, J: 9, K: 10\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: \text{null}, I: K, J: G, K: J\};$

— $S = \{E, G, D, A, F, J, C, K\}$ .

Обработка вершины $B$ .

— $B$ соединена с $H$ (вес 9):

— $d[H] = 21$ , $p[H] = B$ (обновление: $12 + 9 < \infty$ ).

— Обновлённые значения:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: 21, I: 12, J: 9, K: 10\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: B, I: K, J: G, K: J\};$

— $S = \{E, G, D, A, F, J, C, K, B\}$ .

Обработка вершины $I$ .

— $I$ соединена с $C$ (вес 7), $F$ (вес 8), $G$ (вес 7), $H$ (вес 4):

— $d[H] = 16$ , $p[H] = I$ (обновление: $12 + 4 < 21$ ).

— Обновлённые значения:

$d = \{A: 8, B: 12, C: 10, D: 7, E: 0, F: 8, G: 6, H: 16, I: 12, J: 9, K: 10\};$

$p = \{A: D, B: A, C: A, D: E, E: \text{null}, F: G, G: E, H: I, I: K, J: G, K: J\};$

— $S = \{E, G, D, A, F, J, C, K, B, I\}$ .

Обработка вершины $H$ .

— $H$ не соединена ни с какими вершинами, которые могут улучшить пути.

— $S = \{E, G, D, A, F, J, C, K, B, I\}$ .

Для восстановления пути от $E$ до $H$ необходимо проанализировать массив $p$ , который содержит предшественников вершин.

Итак, массив $p$ у нас следующий:

— $p[A] = D$ ;

— $p[B] = A$ ;

— $p[C] = A$ ;

— $p[D] = E$ ;

— $p[E] = \text{null}$ ;

— $p[F] = G$ ;

— $p[G] = E$ ;

— $p[H] = I$ ;

— $p[I] = K$ ;

— $p[J] = G$ ;

— $p[K] = J$ .

Чтобы найти путь от $E$ до $H$ , начнем с вершины $H$ и будем следовать предшественникам до вершины $E$ .

Вершина $H$ : предшественником вершины $H$ является вершина $I$ .

Вершина $I$ : предшественник $I$ — $K$ .

Вершина $K$ : предшественник $K$ — $J$ .

Вершина $J$ : предшественник $J$ — $G$ .

Вершина $G$ : предшественник $G$ — $E$ .

Вершина $E$ : предшественник $E$ — $\text{null}$ (начальная вершина).

Результат:

— кратчайший путь от $E$ до $H$ : $E \rightarrow G \rightarrow J \rightarrow K \rightarrow I \rightarrow H$ ;

— общая длина пути: 16.

Табличный способ

Реализация алгоритма Дейкстры табличным способом представлена в виде таблицы 1.5.11.

Таблица 1.5.11 — Алгоритм Дейкстры

Ответ. Расстояние между вершинами — 16; кратчайший путь, найденный согласно алгоритму Дейкстры: E, G, J, K, I, H.

Рисунок 1.5.15 – Кратчайший путь от E до H - Теория графов polenet.ru — Рисунок 1.5.15 – Кратчайший путь от E до H

Задача 1.5.3. Найти кратчайший путь, используя алгоритм Дейкстры от вершины B до вершины K.

Рисунок 1.5.16 – Взвешенный граф - Теория графов polenet.ru — Рисунок 1.5.16 – Взвешенный граф

Решение.

Итеративный метод

Входные данные:

— A соединена с B (вес 4), C (вес 4), D (вес 1);

— B соединена с A (вес 4), H (вес 7);

— C соединена с A (вес 4), F (вес 4), I (вес 4);

— D соединена с A (вес 1), F (вес 5), E (вес 4);

— E соединена с D (вес 4), G (вес 6);

— F соединена с C (вес 4), D (вес 5), G (вес 1), I (вес 8);

— G соединена с E (вес 6), F (вес 1), J (вес 3), I (вес 4);

— H соединена с B (вес 7), I (вес 6);

— I соединена с C (вес 4), F (вес 8), G (вес 4), H (вес 6), K (вес 7);

— J соединена с G (вес 3), K (вес 3);

— K соединена с I (вес 7), J (вес 3).

Алгоритм Дейкстры от вершины B до вершины K.

Начальная инициализация:

$d = \{A: \infty, B: 0, C: \infty, D: \infty, E: \infty, F: \infty, G: \infty, H: \infty, I: \infty, J: \infty, K: \infty\};$

$p = \{A: \text{null}, B: \text{null}, C: \text{null}, D: \text{null}, E: \text{null}, F: \text{null}, G: \text{null}, H: \text{null}, I: \text{null}, J: \text{null}, K: \text{null}\};$

— $S = \{\}$ .

Обработка вершины B:

— $S = \{B\}$ ;

— вершины, смежные с B: A (вес 4), H (вес 7);

— $d[A] = 4$ , $p[A] = B$ ;

— $d[H] = 7$ , $p[H] = B$ ;

$d = \{A: 4, B: 0, C: \infty, D: \infty, E: \infty, F: \infty, G: \infty, H: 7, I: \infty, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: \text{null}, D: \text{null}, E: \text{null}, F: \text{null}, G: \text{null}, H: B, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Обработка вершины A:

— $S = \{B, A\}$ ;

— вершины, смежные с A: B (вес 4), C (вес 4), D (вес 1);

— вершина B обработана, ее уже на рассматриваем, в дальнейшем обработанные вершины будем пропускать;

— $d[C] = 8$ , $p[C] = A$ ;

— $d[D] = 5$ , $p[D] = A$ ;

$d = \{A: 4, B: 0, C: 8, D: 5, E: \infty, F: \infty, G: \infty, H: 7, I: \infty, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: \text{null}, F: \text{null}, G: \text{null}, H: B, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Обработка вершины D:

— $S = \{B, A, D\}$ ;

— вершины, смежные с D: A (вес 1), F (вес 5), E (вес 4);

— $d[F] = 10$ , $p[F] = D$ ;

— $d[E] = 9$ , $p[E] = D$ ;

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: \infty, H: 7, I: \infty, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: \text{null}, H: B, I: \text{null}, J: \text{null}, K: \text{null}\}.$

Обработка вершины H:

— $S = \{B, A, D, H\}$ ;

— вершины, смежные с H: B (вес 7), I (вес 6);

— $d[I] = 13$ , $p[I] = H$ ;

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: \infty, H: 7, I: 13, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: \text{null}, H: B, I: H, J: \text{null}, K: \text{null}\}.$

Обработка вершины C:

— $S = \{B, A, D, H, C\}$ ;

— вершины, смежные с C: A (вес 4), F (вес 4), I (вес 4);

— $d[F] = 10$ (не обновляется, так как 8 + 4 = 12 не меньше 10);

— $d[I] = 12$ , $p[I] = C$ (обновляется, так как 8 + 4 = 12 меньше 13);

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: \infty, H: 7, I: 12, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: \text{null}, H: B, I: C, J: \text{null}, K: \text{null}\}.$

Обработка вершины E:

— $S = \{B, A, D, H, C, E\}$ ;

— вершины, смежные с E: D (вес 4), G (вес 6);

— $d[G] = 15$ , $p[G] = E$ ;

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: 15, H: 7, I: 12, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: E, H: B, I: C, J: \text{null}, K: \text{null}\}.$

Обработка вершины F:

— $S = \{B, A, D, H, C, E, F\}$ ;

— вершины, смежные с F: C (вес 4), D (вес 5), G (вес 1), I (вес 8);

— $d[G] = 11$ , $p[G] = F$ (обновляется, так как 10 + 1 = 11 меньше 15);

— $d[I] = 18$ (не обновляется, так как 10 + 8 = 18 не меньше 12);

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: 11, H: 7, I: 12, J: \infty, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: F, H: B, I: C, J: \text{null}, K: \text{null}\}.$

Обработка вершины G:

— $S = \{B, A, D, H, C, E, F, G\}$ ;

— вершины, смежные с G: E (вес 6), F (вес 1), J (вес 3), I (вес 4);

— $d[J] = 14$ , $p[J] = G$ (обновляется, так как 11 + 3 = 14 меньше $\infty$ );

— $d[I] = 15$ (не обновляется, так как 11 + 4 = 15 не меньше 12);

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: 11, H: 7, I: 12, J: 14, K: \infty\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: F, H: B, I: C, J: G, K: \text{null}\}.$

Обработка вершины I:

— $S = \{B, A, D, H, C, E, F, G, I\}$ ;

— вершины, смежные с I: C (вес 4), F (вес 8), G (вес 4), H (вес 6), K (вес 7);

— $d[K] = 19$ , $p[K] = I$ (обновляется, так как 12 + 7 = 19 меньше $\infty$ );

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: 11, H: 7, I: 12, J: 14, K: 19\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: F, H: B, I: C, J: G, K: I\}.$

Обработка вершины J:

— $S = \{B, A, D, H, C, E, F, G, I, J\}$ ;

— Вершины, смежные с J: G (вес 3), K (вес 3);

— $d[K] = 17$ , $p[K] = J$ (обновляется, так как 14 + 3 = 17 меньше 19);

$d = \{A: 4, B: 0, C: 8, D: 5, E: 9, F: 10, G: 11, H: 7, I: 12, J: 14, K: 17\};$

$p = \{A: B, B: \text{null}, C: A, D: A, E: D, F: D, G: F, H: B, I: C, J: G, K: J\}.$

Все вершины обработаны, теперь необходимо установить кратчайший путь от вершины B до вершины K. Чтобы найти кратчайший путь, мы проследуем по обратным ссылкам в массиве $p$ от K до B:

— $K\left( p[K] = J \right)$ ;

— $J\left( p[J] = G \right)$ ;

— $G\left( p[G] = F \right)$ ;

— $F\left( p[F] = D \right)$ ;

— $D\left( p[D] = A \right)$ ;

— $A\left( p[A] = B \right)$ .

Таким образом, кратчайший путь от B до K: $B \rightarrow A \rightarrow D \rightarrow F \rightarrow G \rightarrow J \rightarrow K$ ; минимальная сумма весов (расстояние): $d[K] = 17$ .