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

Авторы
Файлы

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

31 08 2026 5:45:35

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

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

30 08 2026 21:55:49

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

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

29 08 2026 10:39:26

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

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

28 08 2026 1:32:51

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

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

27 08 2026 0:13:28

Сувенирная кукла в историческом костюме

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

26 08 2026 19:49:54

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

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

25 08 2026 3:31:57

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

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

24 08 2026 18:15:51

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

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

23 08 2026 2:28:16

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

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

22 08 2026 7:23:11

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

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

21 08 2026 5:28:35

НАРКОМАНИЯ И БЕРЕМЕННОСТЬ

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

20 08 2026 21:57:13

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

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

19 08 2026 3:13:31

Изучение состава сточных вод и возможных путей утилизации побоч-ных продуктов при получении магнитных жидкостей

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

18 08 2026 9:59:43

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

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

17 08 2026 22:13:13

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

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

16 08 2026 9:47:27

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

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

15 08 2026 5:53:31

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

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

14 08 2026 17:41:32

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

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

13 08 2026 1:36:57

УПРАВЛЕНИЕ ИННОВАЦИОННЫМИ ПРОЦЕССАМИ (учебное пособие)

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

12 08 2026 7:37:24

Глобальный инновационный индекс: относительные показатели рейтинга стран

Приведены закономерности рангового распределения по рейтингу 110 стран, среди них Россия занимала 49-е место. Для анализа были приняты показатели: 1) инновационные затраты/суммарный балл; 2) инновационная эффективность/суммарный балл); 3) инновационная эффективность/инновационные затраты. Сравнение показывает весьма скромную инновационную активность России, но при этом значения всех трех относительных показателей инновационной активности у России положительные или позитивные. Только изобретения имеют мировую новизну и достаточно высокую конкурентоспособность, а полезные модели нужны в основном для внутреннего употрeбления. В итоге в стране образуется так называемый инновационный крест. Динамика изобретений куда значимее, если при этом снизить справедливое в неспокойной экономике колебательное возмущение изобретателей. ...

11 08 2026 16:31:58

К изучению почвенных водорослей охраняемых территорий Северо-Западного Кавказа

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

10 08 2026 18:26:56

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

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

09 08 2026 11:55:33

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

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

08 08 2026 23:29:29

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

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

07 08 2026 16:39:44

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

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

06 08 2026 14:54:39

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

Проведено поэтапное исследование, которое включало в себя оценку индивидуальных резервов соматического здоровья (СЗ) и оценку функционального состояния вегетативной нервной системы на основе исследования вариабельности ритма сердца (ВРС). Уровень СЗ оценивался в баллах. В результате проведенного нами исследования было выявлено, что риск манифестации хронической сосудистой патологии достаточно высок в группе с низкими энергетическими резервами организма (уровнем здоровья «низким» и «ниже среднего»), а таковых у нас оказалось 54,5 % из всех обследованных студентов БелГУ. Следующим этапом исследования была проверка этой версии. При анализе вариабельности сердечного ритма учитывались: показатель общей мощности спектра нейрогумopaльной регуляции сердечного ритма (TP); показатель, отражающий реактивность парасимпатического отдела вегетативной нервной системы при проведении АОП; визуальная оценка степени кардио-респираторной синхронизации на основании данных спектрального анализа ВРС и пневмограммы. У обследуемых с низким уровнем соматического здоровья признаки вегетативной дисфункции различной степени выраженности наблюдались в 92,5 % случаев. В группе с низким уровнем СЗ реактивность парасимпатического отдела ВНС, отражающая адаптационные резервы организма, оказалась так же низкой. Таким образом, наша версия о взаимосвязи уровня соматического здоровья и частотой встречаемости вегетативной дисфункции полностью подтвердилась. Чем ниже уровень соматического здоровья, тем более вероятна манифестации хронической сосудистой патологии. При высоком уровне здоровья риск возникновения хронической соматической патологии минимален. ...