МЕТОДЫ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ МЕЖДУ ВЕРШИНАМИ ГРАФА

Авторы
Файлы

Зябиров Э.В. Токарев С.П. Федосеева Л.И. Статья в формате PDF 310 KB

Анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа, позволил выявить алгоритмы Уоршолла, Дейкстры, Форда [1]. Все алгоритмы хаpaктеризуются разными вычислительными затратами и позволяют решать поставленную задачу, но наиболее эффективным считается алгоритм Дейкстры, предложенный в 1959 году.

Перед началом выполнения алгоритма все вершины и дуги не отмечены. Каждой вершине в ходе выполнения алгоритма присваивается число d(x_i), равное длине кратчайшего пути из x_iв x_j, включающего только отмеченные вершины.

Выполняется присвоение начальных значений, для чего необходимо обозначить d(x_i) пометку исходной вершины и считать, что d(x_i) = 0. Отметить постоянной пометкой исходную вершину x_i и положить y = x_i, где y - последняя из отмеченных вершин. Остальные вершины имеют временные пометки и считать, что для x_j ≠ y d(x_j) = ∞. Алгоритм итерационный. Каждая итерация состоит из ряда шагов. Алгоритм Дейкстры рассмотрен на примере взвешенного графа (рис. 1,a). Матрица весов дуг приведена на рис. 1,b. Требуется найти кратчайший путь от вершины x₁ до вершины x₆.

Рис. 1. Пример поиска кратчайшего пути: a - граф; б - матрица весов дуг

Выполняется присвоение начальных значений: d(x₁) = 0; x_i ≠ x₁ d(x_i) = ∞.

Для каждой итерации, в соответствующую строку таблицы заносится отмеченная вершина и текущие значения d(x_i). Для 1-й итерации будем иметь:

y = x₁. Г(x₁) = {x₂, x₃, x₄}.

Для всех вершин, входящих в Г(x₁), пометки которых временные, необходимо пересчитать d(x_i) в виде:

d(x₂) = min [d(x₂), d(x₁) + t(x₁, x₂)] = min [∞, 0 + 4] = 4.

Аналогично для d(x₃), d(x₄). Массив временных пометок будет иметь вид: {d(x₂), d(x₃), d(x₄)} = 4, 3, 7}.

Поскольку величина d(x₃) = 3 является минимальной, то вершина x₃ отмечается x₃*. Также отмечается и дуга (x₁, x₃)*. Наименьшее из значений d(xi) среди неотмеченных вершин в таблице выделено полужирным шрифтом.

Текущее дерево кратчайших путей состоит из дуги (x₁, x₃)* (рис. 2,а).

Таким образом, выполнив еще 4 итерации, получим окончательно построенное дерево кратчайших путей, которое состоит из дуг (x₁, x₃)*, (x₁, x₂)*, (x₃, x₅)*, (x₂, x₄)* и (x₅, x₆)* (рис. 2,д).

а б в г д
Рис. 2. Текущие деревья кратчайшего пути ─ a, б, в, г и окончательно построенное дерево кратчайших путей ─ д

Вычисления по алгоритму Дейкстры

Итерация	Отмеченная вершина	Расстояние до вершины
Итерация	Отмеченная вершина	d(x₁)	d(x₂)	d(x₃)	d(x₄)	d(x₅)	d(x₆)
Начало	x₁	0	∞	∞	∞	∞	∞
1 итерация	x₁*	0	4	3	7	∞	∞
2 итерация	x₃*	0	4	3*	7	6	∞
3 итерация	x₂*	0	4*	3*	7	6	∞
4 итерация	x₅*	0	4*	3*	7	6*	8
5 итерация	x₄*	0	4*	3*	7*	6*	8

Кратчайший путь, соединяющий вершину x₁ с вершиной x₆, состоит из дуг (x₁, x₂), (x₂, x₅) и (x₅, x₆) имеет длину 4 + 2 + 2 = 8. Это не единственный кратчайший путь между вершинами x1 и x6. Путь, состоящий из дуг (x₁, x₃), (x₃, x₅) и (x₅, x₆) имеет длину 3 + 3 + 2 = 8 и также является кратчайшим путем между вершинами x₁ и x₆.

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

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

Список литературы

1. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981. - 324 с.

2. Новиков Ф.А. Дискретная математика для программистов. - СПб: Питер, 2000. - 304 с.

3. Хаггарти Р. Дискретная математика для программистов. - М.: Техносфера, 2005. - 400 с.

ИНТЕРАКТИВНЫЕ ПРОФОРИЕНТАЦИОННЫЕ ИГРЫ КАК СРЕДСТВО ФОРМИРОВАНИЯ ГОТОВНОСТИ К ВЫБОРУ ПРОФЕССИИ У ВЫПУСКНИКОВ 9-11 КЛАССОВ ДЕТСКОГО ДОМА

Статья в формате PDF 124 KB...

22 05 2026 1:38:59

КЛЕТКИ СТЕКЛОВИДНОГО ТЕЛА ГЛАЗА ЧЕЛОВЕКА

Статья в формате PDF 140 KB...

21 05 2026 16:59:36

ЭКОЛОГИЧЕСКАЯ ОЦЕНКА КАЧЕСТВА ПИТЬЕВОЙ ВОДЫ В РАЗЛИЧНЫХ ИСТОЧНИКАХ Г.О. ШУЯ

Статья в формате PDF 300 KB...

20 05 2026 19:27:53

Сравнительная хаpaктеристика регенерации наружного сфинктера прямой кишки при различных видах повреждения

Статья в формате PDF 102 KB...

19 05 2026 0:44:22

ПРЕПОДАВАНИЕ КУРСА «ПЕДАГОГИЧЕСКИЕ ТЕХНОЛОГИИ В ОБУЧЕНИИ ХИМИИ» ДЛЯ МАГИСТРОВ

Статья в формате PDF 161 KB...

18 05 2026 18:33:10

НОВАЯ ПЕРСПЕКТИВНАЯ ТЕХНОЛОГИЯ ИЗГОТОВЛЕНИЯ ТЕЛ НАКАЛА ЛАМП НАКАЛИВАНИЯ

Статья в формате PDF 120 KB...

17 05 2026 2:58:34

ИММУНОГИСТОХИМИЧЕСКАЯ ХАРАКТЕРИСТИКА АДЕНОГИПОФИЗА ПРИ ХРОНИЧЕСКОМ СТРЕССЕ НА РАННИХ ЭТАПАХ ОНТОГЕНЕЗА

Статья в формате PDF 111 KB...

16 05 2026 8:51:58

СУБЪЕКТ ПРАВОНАРУШЕНИЯ ПО ДЕЛАМ ОБ АДМИНИСТРАТИВНЫХ ПРАВОНАРУШЕНИЯХ В ОБЛАСТИ ДОРОЖНОГО ДВИЖЕНИЯ

Статья в формате PDF 277 KB...

15 05 2026 3:23:23

ПРОТИВОРЕЧИЯ МЕЖДУ ФУНКЦИОНИРОВАНИЕМ И РАЗВИТИЕМ СОЦИАЛЬНО-ЭКОНОМИЧЕСКОЙ СИСТЕМЫ КАК ГЕНЕТИЧЕСКАЯ ОСНОВА КРИЗИСОВ

Статья в формате PDF 283 KB...

14 05 2026 14:46:32

«ЦВЕТНЫЕ» СИМПТОМЫ В ПРАКТИЧЕСКОЙ МЕДИЦИНЕ

Статья в формате PDF 173 KB...

13 05 2026 2:58:37

СРЕДСТВА СОЗДАНИЯ ВИРТУАЛЬНЫХ РЕАЛЬНОСТЕЙ

Статья в формате PDF 254 KB...

12 05 2026 17:31:47

ДВИЖЕНИЕ ЗА ЦЕЛОСТНОСТЬ КАК ОДНО ИЗ НАПРАВЛЕНИЙ РАЗВИТИЯ СОВРЕМЕННОЙ НАУКИ И ОБРАЗОВАНИЯ

Статья в формате PDF 105 KB...

11 05 2026 12:22:46

АНАЛИЗ РАЗВИТИЯ СТРАХОВАНИЯ В СССР

Статья в формате PDF 310 KB...

10 05 2026 0:34:48

ИССЛЕДОВАНИЕ МИКРОМЕХАНИЗМОВ ПОВРЕЖДАЕМОСТИ ДИФФУЗИОННЫХ ЗОН ПОСЛЕ НИКОТРИРОВАНИЯ

Статья в формате PDF 94 KB...

09 05 2026 21:40:48

Имидж профессиональной деятельности специалистов социальной сферы (учебное пособие)

Статья в формате PDF 302 KB...

08 05 2026 10:36:49

СТАНДАРТИЗАЦИЯ СОЦИАЛЬНОЙ РЕКЛАМЫ

Статья в формате PDF 182 KB...

07 05 2026 19:31:24

К ВОПРОСУ ОБ АЛГОРИТМИЗАЦИИ ФАРМАКОЭКОНОМИКИ КАРДИОЛОГИЧЕСКИХ ПРЕПАРАТОВ В ПРАКТИКЕ ВРАЧА СКОРОЙ МЕДИЦИНСКОЙ ПОМОЩИ

Статья в формате PDF 116 KB...

06 05 2026 21:31:13

Коррекция экстpaктом пятилистника кустарникового вторичных иммунодефицитных состояний

Статья в формате PDF 111 KB...

05 05 2026 17:29:45

АКТИВНЫЕ МЕТОДЫ ОБУЧЕНИЯ

Статья в формате PDF 249 KB...

04 05 2026 8:13:36

ФОЛЬКЛОР КАК СРЕДСТВО ФОРМИРОВАНИЯ МУЗЫКАЛЬНОЙ КУЛЬТУРЫ ЧЕЛОВЕКА И ПЕДАГОГА

Статья в формате PDF 142 KB...

03 05 2026 16:20:52

ВТОРИЧНЫЕ ПРОДУКТЫ УБОЯ ЖИВОТНЫХ В ПРОЕКТИРОВАНИИ КИСЛОРОДНЫХ КОКТЕЙЛЕЙ КАК ИННОВАЦИОННЫХ ПРОДУКТОВ

Статья в формате PDF 253 KB...

02 05 2026 18:38:33

КОРРУПЦИОННЫЙ ХАРАКТЕР ПРОБЛЕМ УСЫНОВЛЕНИЯ РОССИЙСКИХ ДЕТЕЙ ИНОСТРАНЦАМИ

Статья в формате PDF 286 KB...

01 05 2026 2:12:36

СПОСОБ ПЛАЗМЕННОЙ СВАРКИ НА ПЕРЕМЕННОМ ТОКЕ

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