МЕТОДЫ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ МЕЖДУ ВЕРШИНАМИ ГРАФА
Анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа, позволил выявить алгоритмы Уоршолла, Дейкстры, Форда [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
112 KB...
12 06 2026 11:16:25
Статья в формате PDF
496 KB...
11 06 2026 15:43:12
Статья в формате PDF
119 KB...
10 06 2026 17:33:35
Статья в формате PDF
148 KB...
08 06 2026 4:50:50
Статья в формате PDF
132 KB...
07 06 2026 18:56:48
Статья в формате PDF
110 KB...
06 06 2026 17:33:35
Данная статья посвящена актуальной проблеме – развитию селезенки как органа иммунной системы на этапах постнатального онтогенеза. Приведен сравнительный анализ литературных источников по постнатальному развитию селезенки. В работах отмечается разноречивость некоторых суждений исследователей, касающихся органогенеза и гистогенеза данного органа.
...
05 06 2026 6:49:22
Химия, биология, география и астрономия являются естественными науками, а обучение химии, биологии, географии и астрономии, безусловно, является искусством. И от того, насколько педагоги владеют этим искусством, зависит то, насколько наше общество вооружено знаниями. Обучение естественным наукам - это не просто передача определенного объема знаний, но и развитие жажды серьезного труда, без которой жизнь не может быть ни достойной, ни счастливой. А для того, чтобы эта жажда появилась, необходимо, чтобы сам напиток знаний был не только полезным и поучительным, но и обязательно «вкусным», содержал какие-то «наркотические компоненты», вызывающие устойчивое привыкание к получению все новых знаний. Талантливым детям необходимы талантливые учебники и талантливые образовательные системы. Нельзя сокращать количество часов преподавания естественнонаучных дисциплин, которые способствуют лучшему усвоению гуманитарных предметов, воспитывают логику, необходимую для обучения точным дисциплинам, способствуют воспитанию гуманизма. Приводится перечень проблем, которые необходимо решать при построении образовательной системы становления естественнонаучного мировоззрения у одаренных детей.
...
04 06 2026 10:43:15
Статья в формате PDF
108 KB...
03 06 2026 23:10:32
Статья в формате PDF
120 KB...
02 06 2026 8:40:13
Статья в формате PDF
184 KB...
01 06 2026 21:57:53
Статья в формате PDF
119 KB...
31 05 2026 2:16:38
Статья в формате PDF
274 KB...
30 05 2026 14:13:21
Статья в формате PDF
295 KB...
29 05 2026 23:57:11
Статья в формате PDF
529 KB...
28 05 2026 18:21:40
В статье рассматривается взаимодействие тел при различных скоростях и делается вывод о несправедливости постулата о постоянстве скорости света относительно любой системы отсчета. Дается также понятное с точки зрения классической механики объяснение зависимости длины и времени от скорости.
...
27 05 2026 1:27:13
Статья в формате PDF
110 KB...
26 05 2026 12:28:49
Статья в формате PDF
123 KB...
25 05 2026 17:13:30
Статья в формате PDF
105 KB...
24 05 2026 0:18:16
Статья в формате PDF
170 KB...
23 05 2026 19:49:56
Статья в формате PDF 124 KB...
22 05 2026 17:18:20
Статья в формате PDF
162 KB...
20 05 2026 2:47:31
Статья в формате PDF
263 KB...
19 05 2026 16:41:31
Статья в формате PDF
120 KB...
18 05 2026 20:41:24
Статья в формате PDF
144 KB...
16 05 2026 11:44:46
Вовлечение серой лесной почвы в сельскохозяйственное производство в течение 26 лет приводит к формированию специфических свойств, которые обусловлены преобразованием микроагрегированности почв. Активность этого процесса зависит от типа агрогенной нагрузки. Так механическое воздействие на серую лесную почву в результате ежегодной отвальной вспашки на 20–22 см вызывает изменение коэффициента полидисперсности и фактора дисперсности в слое 30–40 см. Применение ежегодной безотвальной обработки на глубину 6–8 см не оказывает существенного влияние на микроагрегированность почвы, что не приводит к формированию плужной подошвы.
...
15 05 2026 1:26:28
Статья в формате PDF
114 KB...
14 05 2026 9:58:21
Статья в формате PDF
119 KB...
13 05 2026 10:49:15
Статья в формате PDF
129 KB...
12 05 2026 1:22:11
Статья в формате PDF
401 KB...
11 05 2026 9:57:33
Статья в формате PDF
286 KB...
10 05 2026 21:59:47
Статья в формате PDF
107 KB...
09 05 2026 5:39:51
Статья в формате PDF
121 KB...
08 05 2026 5:30:10
Статья в формате PDF
142 KB...
07 05 2026 12:17:51
Статья в формате PDF
293 KB...
06 05 2026 4:13:29
Статья в формате PDF
108 KB...
05 05 2026 14:18:42
Статья в формате PDF
133 KB...
04 05 2026 18:44:14
Еще:
Поддержать себя -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 ::
