МЕТОДЫ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ МЕЖДУ ВЕРШИНАМИ ГРАФА
Анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа, позволил выявить алгоритмы Уоршолла, Дейкстры, Форда [1]. Все алгоритмы хаpaктеризуются разными вычислительными затратами и позволяют решать поставленную задачу, но наиболее эффективным считается алгоритм Дейкстры, предложенный в 1959 году.
Перед началом выполнения алгоритма все вершины и дуги не отмечены. Каждой вершине в ходе выполнения алгоритма присваивается число d(xi), равное длине кратчайшего пути из xi в xj, включающего только отмеченные вершины.
Выполняется присвоение начальных значений, для чего необходимо обозначить d(xi) пометку исходной вершины и считать, что d(xi) = 0. Отметить постоянной пометкой исходную вершину xi и положить y = xi, где y - последняя из отмеченных вершин. Остальные вершины имеют временные пометки и считать, что для xj ≠ y d(xj) = ∞. Алгоритм итерационный. Каждая итерация состоит из ряда шагов. Алгоритм Дейкстры рассмотрен на примере взвешенного графа (рис. 1,a). Матрица весов дуг приведена на рис. 1,b. Требуется найти кратчайший путь от вершины x1 до вершины x6.
Рис. 1. Пример поиска кратчайшего пути: a - граф; б - матрица весов дуг
Выполняется присвоение начальных значений: d(x1) = 0; xi ≠ x1 d(xi) = ∞.
Для каждой итерации, в соответствующую строку таблицы заносится отмеченная вершина и текущие значения d(xi). Для 1-й итерации будем иметь:
y = x1. Г(x1) = {x2, x3, x4}.
Для всех вершин, входящих в Г(x1), пометки которых временные, необходимо пересчитать d(xi) в виде:
d(x2) = min [d(x2), d(x1) + t(x1, x2)] = min [∞, 0 + 4] = 4.
Аналогично для d(x3), d(x4). Массив временных пометок будет иметь вид: {d(x2), d(x3), d(x4)} = 4, 3, 7}.
Поскольку величина d(x3) = 3 является минимальной, то вершина x3 отмечается x3*. Также отмечается и дуга (x1, x3)*. Наименьшее из значений d(xi) среди неотмеченных вершин в таблице выделено полужирным шрифтом.
Текущее дерево кратчайших путей состоит из дуги (x1, x3)* (рис. 2,а).
Таким образом, выполнив еще 4 итерации, получим окончательно построенное дерево кратчайших путей, которое состоит из дуг (x1, x3)*, (x1, x2)*, (x3, x5)*, (x2, x4)* и (x5, x6)* (рис. 2,д).
а б в г д
Рис. 2. Текущие деревья кратчайшего пути ─ a, б, в, г и окончательно построенное дерево кратчайших путей ─ д
Вычисления по алгоритму Дейкстры
|
Итерация |
Отмеченная вершина |
Расстояние до вершины |
|||||
|
d(x1) |
d(x2) |
d(x3) |
d(x4) |
d(x5) |
d(x6) |
||
|
Начало |
x1 |
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
1 |
x1* |
0 |
4 |
3 |
7 |
∞ |
∞ |
|
2 |
x3* |
0 |
4 |
3* |
7 |
6 |
∞ |
|
3 |
x2* |
0 |
4* |
3* |
7 |
6 |
∞ |
|
4 |
x5* |
0 |
4* |
3* |
7 |
6* |
8 |
|
5 |
x4* |
0 |
4* |
3* |
7* |
6* |
8 |
Кратчайший путь, соединяющий вершину x1 с вершиной x6, состоит из дуг (x1, x2), (x2, x5) и (x5, x6) имеет длину 4 + 2 + 2 = 8. Это не единственный кратчайший путь между вершинами x1 и x6. Путь, состоящий из дуг (x1, x3), (x3, x5) и (x5, x6) имеет длину 3 + 3 + 2 = 8 и также является кратчайшим путем между вершинами x1 и x6.
Существуют алгоритмы более эффективные, чем процеДypa многократного повторения алгоритма Дейкстры. Эти алгоритмы принадлежат Флойду и Данцигу. В обоих алгоритмах для длин дуг допускаются отрицательные значения, однако не допускается наличие контуров отрицательной длины.
Как видно из описания алгоритмов поиска кратчайших путей, в основном они состоят из операций двух типов: операции сложения и операции сравнения по минимуму. При анализе вычислительной сложности любого из этих алгоритмов обычно предполагается, что для выполнения обеих операций требуется одинаковое время.
Список литературы
1. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981. - 324 с.
2. Новиков Ф.А. Дискретная математика для программистов. - СПб: Питер, 2000. - 304 с.
3. Хаггарти Р. Дискретная математика для программистов. - М.: Техносфера, 2005. - 400 с.
Статья в формате PDF
149 KB...
13 01 2025 8:43:24
Статья в формате PDF
373 KB...
11 01 2025 20:54:15
На основании результатов комплексного клинико- инструментального обследования 390 детей в возрасте от 5 до 15 лет, проживающих в г. Красноярске, была изучена зависимость клинического течения нарушений сердечного ритма и проводимости от выраженности и формы малых аномалий развития сердца. Установлены основные эхокардиографические параметры и прогностические критерии развития гемодинамических нарушений у детей с аритмиями.
...
09 01 2025 17:28:12
Статья в формате PDF
215 KB...
08 01 2025 21:29:13
Статья в формате PDF
292 KB...
06 01 2025 5:38:28
Статья в формате PDF
126 KB...
04 01 2025 5:14:58
Статья в формате PDF
113 KB...
02 01 2025 12:51:14
Статья в формате PDF
172 KB...
01 01 2025 17:39:58
Статья в формате PDF
124 KB...
31 12 2024 7:18:25
В статье раскрываются адаптационная деятельность организма, показано, что функциональная система регуляции кровообращения представляет собой многоконтурную, иерархически организованную систему, в которой доминирующая роль отдельных звеньев определяется текущими потребностями организма.
...
30 12 2024 19:11:57
Статья в формате PDF
224 KB...
28 12 2024 17:47:28
Статья в формате PDF
132 KB...
27 12 2024 23:21:24
Статья в формате PDF
101 KB...
26 12 2024 16:17:46
Статья в формате PDF
115 KB...
25 12 2024 18:13:21
Статья в формате PDF
98 KB...
24 12 2024 10:26:57
Статья в формате PDF
241 KB...
23 12 2024 21:18:13
Статья в формате PDF
112 KB...
22 12 2024 12:49:49
Статья в формате PDF
114 KB...
21 12 2024 15:17:21
Статья в формате PDF
103 KB...
20 12 2024 10:14:15
Статья в формате PDF
117 KB...
19 12 2024 2:38:56
Статья в формате PDF
119 KB...
18 12 2024 15:51:23
Статья в формате PDF
114 KB...
17 12 2024 11:56:46
Статья в формате PDF
258 KB...
15 12 2024 21:28:27
Проведен анализ эффективности различных типов фитнес-программ в коррекции избыточной массы тела женщин юношеского и зрелого возраста. Применяемые физические нагрузки отличались хаpaктером нагрузки и наличию/отсутствию компонента коррекции питания. Исследовали антропометрические показатели, ИМТ, определяли содержание жировой массы в организме методом калипометрии в динамике 6-мecячного тренировочного цикла. Проводили промежуточные исследования: в середине, через 3 месяца от начала тренировочного цикла. В исследовании приняли участие 93 пpaктически здоровые женщины с избыточной массой тела, не имеющие эндокринных заболеваний и противопоказаний к занятиям физической культурой. Выделены группы в зависимости от типа программы (I, II), а также подгруппы (Ia, IIa) в зависимости от возраста: 18–21 год (I и II, n = 17 и n = 17, соответственно) и 36–45 лет (Ia, IIa, n = 30 и n = 29, соответственно). Показана динамика и статистическая значимость различий в группах, проведен сравнительный анализ между группами. Выявлена более высокая физиологическая эффективность программы I, базирующейся на смешанном хаpaктере тренировки, многовариантной схеме упражнений с мониторированием и коррекцией хаpaктера питания.
...
14 12 2024 1:51:29
Статья в формате PDF
129 KB...
12 12 2024 18:50:12
Статья в формате PDF
133 KB...
11 12 2024 8:12:52
Применение хитинсодержащих препаратов оказывает положительное влияние на мясную продуктивность бычков, а превосходство по хаpaктеристикам химического состава и энергетической ценности мякоти имеют бычки, получавшие сукцинат хитозана.
...
10 12 2024 16:25:13
Статья в формате PDF
106 KB...
09 12 2024 16:35:26
Статья в формате PDF
115 KB...
07 12 2024 7:24:51
Статья в формате PDF
264 KB...
06 12 2024 13:21:47
Статья в формате PDF
141 KB...
05 12 2024 7:10:16
Еще:
Поддержать себя -1 :: Поддержать себя -2 :: Поддержать себя -3 :: Поддержать себя -4 :: Поддержать себя -5 :: Поддержать себя -6 :: Поддержать себя -7 :: Поддержать себя -8 :: Поддержать себя -9 :: Поддержать себя -10 :: Поддержать себя -11 :: Поддержать себя -12 :: Поддержать себя -13 :: Поддержать себя -14 :: Поддержать себя -15 :: Поддержать себя -16 :: Поддержать себя -17 :: Поддержать себя -18 :: Поддержать себя -19 :: Поддержать себя -20 :: Поддержать себя -21 :: Поддержать себя -22 :: Поддержать себя -23 :: Поддержать себя -24 :: Поддержать себя -25 :: Поддержать себя -26 :: Поддержать себя -27 :: Поддержать себя -28 :: Поддержать себя -29 :: Поддержать себя -30 :: Поддержать себя -31 :: Поддержать себя -32 :: Поддержать себя -33 :: Поддержать себя -34 :: Поддержать себя -35 :: Поддержать себя -36 :: Поддержать себя -37 :: Поддержать себя -38 ::
