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

Авторы
Файлы

Зябиров Э.В. Токарев С.П. Федосеева Л.И. Статья в формате 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 с.

РАЗРАБОТКА ПРОИЗВОДСТВЕННОЙ И ЭКОЛОГИЧЕСКОЙ БЕЗОПАСНОСТИ ПРИ ПРОВЕДЕНИИ ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА ВЫПЛАВКИ СТАЛИ В СТАЛЕПЛАВИЛЬНОМ ПРОИЗВОДСТВЕ КОЛЕСОПРОКАТНОГО КОМПЛЕКСА ОАО «ВМЗ»

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

10 10 2026 23:12:17

ПАМЯТЬ В ПРОЦЕССЕ ИЗУЧЕНИЯ ИНОСТРАННОГО ЯЗЫКА

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

09 10 2026 20:30:33

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

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

08 10 2026 14:45:41

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

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

07 10 2026 13:40:49

ЭТНОПЕДАГОГИЧЕСКИЕ ВОЗЗРЕНИЯ НАРОДА САХА (НА МАТЕРИАЛЕ ОЛОНХО) (монография)

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

06 10 2026 13:13:48

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

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

05 10 2026 4:48:33

Способы утилизации микрокремнезема в легковесной керамике

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

04 10 2026 8:40:29

АСПЕКТЫ АНАЛИЗА КОММУНИКАЦИИ

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

03 10 2026 2:20:38

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

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

02 10 2026 0:12:30

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

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

01 10 2026 9:29:24

ПРИМЕНЕНИЕ МЕТОДА КОЛИЧЕСТВЕННОЙ МИКРОФЛЮОРИМЕТРИИ ДЛЯ ОПРЕДЕЛЕНИЯ АКТИВНОСТИ ФЕРМЕНТОВ

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

30 09 2026 3:58:35

ПРОБЛЕМА ВОСПИТАНИЯ В УСЛОВИИ ПОСТКОММУНИСТИЧЕСКОГО РАЗВИТИЯ РОССИЙСКОГО ОБЩЕСТВА

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

29 09 2026 14:33:12

ЭКОЛОГО-БИОЛОГИЧЕСКАЯ ХАРАКТЕРИСТИКА ТЕРРИТОРИИ ПРИРОДНОГО ПАРКА «НУМТО» (ХАНТЫ-МАНСИЙСКИЙ АВТОНОМНЫЙ ОКРУГ)

В статье дана комплексная хаpaктеристика природных условий территории природного парка «Нумто»: приводятся сведения по геоморфологии, климату, гидрографии, растительному покрову, фауне уникального участка водно-болотных угодий на стыке подзон северной и средней тайги Западной Сибири. ...

28 09 2026 8:57:35

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

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

27 09 2026 14:34:34

Развивитие функционально-графической грамотности в основной школе

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

26 09 2026 1:39:59

КОНЦЕНТРИРОВАНИЕ ИОНОВ МЕДИ (II) С ПОЛИМЕРНЫМ СОРБЕНТОМ ВОЛОКНИСТОЙ СТРУКТУРЫ

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

25 09 2026 13:33:23

МЕХАНИЗМЫ ЧУВСТВИТЕЛЬНОСТИ К АСПИРИНУ ПРИ АСТМЕ

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

24 09 2026 19:16:12

Возрастные параметры прироста массы тела бычков симментальской породы при смешанной инвазии фасциолеза и дикроцелиоза в Кабардино-Балкарской Республике

В возрастные периоды от 6 до 9 мес. инвазированные смешанной инвазией фасциолеза и дикроцелиоза бычки симментальской породы пастбищного содержания отставали в приросте массы тела на 9,7 %, в возрасте от 12 до 15 мес. на 12,9 % и в возрасте от 15 до 18 мес. на 15,5 %, что отрицательно влияет на убойные и технологические качества животных. ...

23 09 2026 21:41:41

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

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

22 09 2026 5:36:48

СРАВНИТЕЛЬНЫЙ АНАЛИЗ ОРИЕНТИРОВОЧНО-ИССЛЕДОВАТЕЛЬСКОГО ПОВЕДЕНИЯ КРЫС ЛИНИИ ВИСТАР И WAG/RIJ С ГЕНОТИПОМ А1А1 ПО ЛОКУСУ TAQ 1A ДОФАМИНОВОГО РЕЦЕПТОРА ВТОРОГО ТИПА (DRD2)

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