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

Авторы
Файлы

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

02 07 2026 16:26:14

Решение интегральных уравнений операционным методом

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

01 07 2026 12:52:46

ИССЛЕДОВАНИЕ ТЕПЛООБМЕНА ТРУБЧАТОГО ЭЛЕКТРОДА С ОПИЛКАМИ

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

30 06 2026 3:55:42

«Качество жизни» больных ИБС при длительной гиполипидемической фармакотерапии

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

29 06 2026 19:25:23

ЭКОЛОГО-БИОХИМИЧЕСКИЕ ИССЛЕДОВАНИЯ ГИДРОБИОНТОВ – ВАЖНОЕ НАПРАВЛЕНИЕ ДЛЯ РЕШЕНИЯ ПРОБЛЕМЫ СОХРАНЕНИЯ БИОЛОГИЧЕСКОГО РАЗНООБРАЗИЯ ВОДНЫХ ЭКОСИСТЕМ КОЛЬСКОГО СЕВЕРА

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

28 06 2026 8:26:44

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

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

27 06 2026 11:55:39

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

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

26 06 2026 0:27:48

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

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

25 06 2026 17:30:34

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

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

24 06 2026 4:35:24

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

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

23 06 2026 9:33:56

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

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

22 06 2026 18:48:16

К ВОПРОСУ О ПОВЫШЕНИИ ЭФФЕКТИВНОСТИ ИНСТИТУЦИОНАЛЬНОГО УПРАВЛЕНИЯ В ТУРЦИИ

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

21 06 2026 3:52:22

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

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

20 06 2026 9:42:41

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

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

19 06 2026 18:27:24

ТАНГАНОВ БОРИС БАДМАЕВИЧ

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

18 06 2026 6:41:26

ОСНОВЫ ГРАВИТАЦИИ (КРАТКОЕ ИЗЛОЖЕНИЕ)

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

17 06 2026 16:23:32

ХАРАКТЕРИСТИКА ТИПОВ ТЕМПЕРАМЕНТА СТУДЕНТОК 17-22 ЛЕТ ЮГА ТЮМЕНСКОЙ ОБЛАСТИ

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

16 06 2026 10:20:50

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

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

15 06 2026 4:54:17

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

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

14 06 2026 6:52:54

КОНЦЕПЦИЯ СОВРЕМЕННОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

13 06 2026 16:41:44

ВОСТОЧНОЕ ЗАБАЙКАЛЬЕ: ТЕРРИТОРИАЛЬНЫЕ РАЗЛИЧИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО РАЗВИТИЯ

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

12 06 2026 6:19:40

ТРАНСФОРМАЦИЯ ВЗАИМНОЙ ТОРГОВЛИ В СИСТЕМЕ СТРАН БРИКС + ИРАН

С использованием инструмента «Bilateral Trade» базы данных Trade Map проделаны матричный анализ взаимной торговли в системе стран БРИКС + Иран за 2001 и 2010 гг. Расчеты показали на существенную трaнcформацию взаимной торговли в системе рассматриваемых стран, в которой Россия значительно ухудшила свои позиции, а Бразилия и Китай – улучшили. Показано также, что Иран гораздо лучше интегрирован во взаимную торговлю со странами БРИКС по сравнению с ЮАР, что даёт ему весомый аргумент для вступления в это объединение стран. ...