МЕТОДЫ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ МЕЖДУ ВЕРШИНАМИ ГРАФА
Анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа, позволил выявить алгоритмы Уоршолла, Дейкстры, Форда [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
105 KB...
27 04 2024 20:57:39
Статья в формате PDF
129 KB...
26 04 2024 23:25:24
Статья в формате PDF
122 KB...
25 04 2024 9:15:15
Статья в формате PDF
98 KB...
24 04 2024 9:56:52
Статья в формате PDF
253 KB...
23 04 2024 8:42:34
Статья в формате PDF
253 KB...
22 04 2024 10:51:56
Статья в формате PDF
80 KB...
21 04 2024 5:34:56
Статья в формате PDF
369 KB...
20 04 2024 2:55:15
Статья в формате PDF
120 KB...
19 04 2024 4:12:50
Статья в формате PDF
137 KB...
18 04 2024 17:54:38
В работе представлен анализ данных литературы и собственных клинико–лабораторных обследований пациенток с дисфункциональными маточными кровотечениями и подтвержденным диагнозом гиперплазии эндометрия, позволивший дать оценку эпидемиологической ситуации, а также состояния вопроса о классификации и патоморфологической хаpaктеристике различных видов гиперпластических процессов эндометрия.
...
16 04 2024 16:29:17
Статья в формате PDF
206 KB...
15 04 2024 17:35:19
Статья в формате PDF
113 KB...
14 04 2024 7:59:10
Статья в формате PDF
198 KB...
13 04 2024 23:23:11
Статья в формате PDF
119 KB...
12 04 2024 16:59:24
Возникшее при низкодозовом радиационном воздействии повышение уровня ТТГ, снижение уровня тиреоидных гормонов, истощение симпатической импульсации и вегетативный дисбаланс, свидетельствует об установившейся адрено-тиреоидной дисфункции в организме жителей молодого (21–30 лет) и пожилого возраста (61–70 лет) проживающих в районах, прилегающих к Семипалатинскому ядерному полигону.
...
11 04 2024 3:36:26
Изучалось влияние на синаптическую передачу ряда фармакологических препаратов (соланин, дециламин, декаметоний, морфолин, госсипол, пикриновая кислота), имеющих по своей химической структуре общие хаpaктерные функциональные группы, но относящиеся к различным классам соединений. Так как изучение механизма действия исследуемых веществ имеет большое значение для пpaктической медицины и для понимания происходящих процессов в периферической нервной системе, нами была предпринята попытка раскрыть хаpaктер их влияния на освобождение медиатора их нервных окончаний грудной мышцы m. Cutaneus pectoris травяной лягушки Rana temporaria.
...
10 04 2024 0:15:17
Статья в формате PDF
103 KB...
08 04 2024 8:49:51
Статья в формате PDF
115 KB...
07 04 2024 20:38:12
Статья в формате PDF 256 KB...
05 04 2024 11:44:46
Был изучен нутритивный профиль у 55 больных накануне операции микроваскулярной декомпрессии корешка тройничного нерва и в течение первых пяти суток раннего послеоперационного периода. Больные были распределены в две группы, разница в интенсивной терапии между которыми заключалась в использовании парентерального питания до того момента, когда пациент самостоятельно не начинает адекватно питаться и принимать жидкость. Изучались такие параметры, как абсолютное число лимфоцитов, уровни общего белка, альбумина и трaнcферрина плазмы крови. Было достоверно доказано положительное влияние на исходно скомпрометированный нутритивный статус проведения парентерального питания в раннем послеоперационном периоде после данной разновидности нейрохирургических вмешательств.
...
04 04 2024 10:57:36
Рассмотрены проекты, связанные с инновациями. Определены понятия: «проект, содержащий инновацию», «проекты, связанные с инновациями», «проект, вовлекающий инновации». Дана концептуальная схема взаимосвязи проектов, связанных с инновациями. Приведены примеры различных проектов. Показаны различные виды технологических и информационных потоков в комплексе проектов, связанных с инновациями Введено понятие, «среды развития инновации». Рассмотрен пример трaнcпортной инфраструктуры как среды развития инноваций. Определены условия, при которых может возникнуть открытый инновационный проект. Дается схема мониторинга результата инновации. Показано различие между полем отношений и полем взаимодействия среды с результатом инновации. Показано, что комплекс проектов является взаимосвязанным. Поэтому при реализации системы управления инновациями этот комплекс должен быть принят за основу такой системы
...
03 04 2024 20:25:16
Статья в формате PDF
126 KB...
02 04 2024 10:10:13
Статья в формате PDF
312 KB...
01 04 2024 12:18:33
Статья в формате PDF
240 KB...
31 03 2024 11:42:19
Статья в формате PDF
99 KB...
30 03 2024 12:39:54
Статья в формате PDF
264 KB...
29 03 2024 20:35:35
Статья в формате PDF
263 KB...
28 03 2024 2:39:47
Статья в формате PDF
114 KB...
27 03 2024 1:42:28
Учебный предмет география состоит из двух блоков. Физическая география изучает элементы природы как единое целое, формирует “образ территории”. Социально-экономическая география рассматривает развитие общества и экономики в тесной взаимосвязи с природными условиями. Для формирования и поддержания интереса к географии в ФТЛ № 1 широко используются современные информационные технологии. Компьютерное тестирование систематически используется на уроках. Лицеисты успешно участвуют в различных телекоммуникационных олимпиадах - индивидуальных и групповых конкурсах с использованием электронной почты и сети Интернет. Такие проекты развивают умение работать с различными источниками информации, способствуют межпредметной интеграции знаний и формированию целостной картины мира.
...
26 03 2024 7:15:35
Статья в формате PDF
312 KB...
25 03 2024 19:43:50
Статья в формате PDF
110 KB...
23 03 2024 8:26:29
Статья в формате PDF
987 KB...
22 03 2024 2:59:26
Статья в формате PDF
122 KB...
21 03 2024 22:11:42
Статья в формате PDF
113 KB...
19 03 2024 22:29:20
Еще:
Поддержать себя -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 ::
