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

Авторы
Файлы

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

30 10 2026 22:28:30

Особенности организации женского организма и сущность перестройки его при беременности в аспектах эволюционной физиологии

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

29 10 2026 21:14:41

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

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

28 10 2026 12:40:18

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

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

27 10 2026 2:48:37

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

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

26 10 2026 3:10:36

ИНСУЛИНДЕГРАДИРУЮЩАЯ АКТИВНОСТЬ ЭРИТРОЦИТОВ У ПОДРОСТКОВ С ПОВЫШЕННОЙ МАССОЙ ТЕЛА

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

25 10 2026 20:49:19

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

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

24 10 2026 10:39:34

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

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

23 10 2026 1:26:23

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

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

22 10 2026 3:10:12

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

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

21 10 2026 18:41:39

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

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

20 10 2026 10:13:29

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

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

19 10 2026 17:37:12

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

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

18 10 2026 9:49:18

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

По материалам геоботанических исследований растительного покрова на отвалах горных пород Кузнецкого угольного бассейна проведен таксономический анализ флористических списков трех стадий восстановительной сукцессии. Определены зональные особенности сукцессионных процессов. Установлены наиболее активные виды с высокими показателями встречаемости. ...

17 10 2026 13:29:55

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

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

16 10 2026 9:10:37

ДИСТАНЦИОННОЕ УПРАВЛЕНИЕ ЗДОРОВЬЕМ ЧЕЛОВЕКА С ПОМОЩЬЮ КВАНТОВО-ВОЛНОВЫХ ФИЗИОЛОГИЧЕСКИХ ТЕХНОЛОГИЙ (КВАНТОВО-ВОЛНОВАЯ ФИЗИОЛОГИЯ)

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

15 10 2026 11:11:57

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

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

14 10 2026 10:36:36

Новые аспекты хирургического лечения послеоперационных вентральных грыж у пациентов с онкопатологией пищеварительного тpaкта

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

13 10 2026 21:23:33

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

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

12 10 2026 5:27:21

КЛЕЩЕВОЙ ЭНЦЕФАЛИТ И БОРРЕЛИОЗ (ДИАГНОСТИКА, ИММУНОТЕРАПИЯ)

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

11 10 2026 3:15:20

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

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

10 10 2026 8:10:11

КЛАССИФИКАЦИЯ БОЛЬНЫХ, СТРАДАЮЩИХ ХРОНИЧЕСКОЙ СЕРДЕЧНОЙ НЕДОСТАТОЧНОСТЬЮ МЕТОДОМ «ДЕРЕВЬЯ КЛАССИФИКАЦИИ»

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

09 10 2026 12:21:35

Экобиоморфный состав флоры мелов

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

08 10 2026 11:16:19

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

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

07 10 2026 6:15:34

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

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

06 10 2026 3:30:42

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

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