Задача сведения минимума. Кратчайшие пути в графах
![]()
|
Часть 3. Кратчайшие пути в графахЗадание 1. Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, используя алгоритм Дейкстры. Построить дерево кратчайших путей. Отрицательные длины в матрице заменить положительными. Задание 2. Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, пользуясь алгоритмом Беллмана. Построить дерево кратчайших путей. ![]() Алгоритм Дейкстры
Заполняем вторую строку таблицы 𝑑(2) = min(∞; 0 + 10) = 10 𝑑(4) = min(∞; 0 + 8) = 8 𝑑(5) = min(∞; 0 + 6) = 6 𝑑(7) = min(∞; 0 + 5) = 5 𝑑(8) = min(∞; 0 + 4) = 4 𝑝 = 8 Заполняем третью строку таблицы 𝑑(4) = min(8; 4 + 10) = 8 𝑑(7) = min(5; 4 + 5) = 5 𝑝 = 7 Заполняем четвёртую строку таблицы 𝑑(2) = min(10; 5 + 3) = 8 𝑑(4) = min(8; 5 + 2) = 7 𝑝 = 5 Заполняем пятую строку таблицы 𝑑(3) = min(∞; 6 + 5) = 11 𝑑(9) = min(∞; 6 + 5) = 11 𝑝 = 2 Заполняем шестую строку таблицы 𝑑(3) = min(11; 8 + 3) = 11 𝑑(4) = min(7; 8 + 3) = 7 𝑑(6) = min(∞; 8 + 2) = 10 𝑑(9) = min(11; 8 + 8) = 11 𝑝 = 4 Заполняем седьмую строку таблицы 𝑑(6) = min(∞; 7 + 2) = 9 𝑝 = 6 Заполняем восьмую строку таблицы 𝑑(3) = min(11; 9 + 8) = 11 𝑑(9) = min(11; 9 + 1) = 10 𝑑(10) = min(∞; 9 + 1) = 10 𝑝 = 10 Заполняем девятую строку таблицы 𝑑(9) = min(10; 10 + 5) = 10 𝑝 = 9 Остаётся p = 3. Дерево кратчайших путей: |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 0 | 10 | ∞ | 8 | 6 | ∞ | 5 | 4 | ∞ | ∞ |
2 | 0 | 2 | 11 | 3 | 6 | 6 | 5 | 4 | 11 | ∞ |
3 | 0 | 2 | 5 | 3 | 6 | 1 | 5 | 4 | 10 | 17 |
4 | 0 | 2 | 5 | 3 | 6 | 1 | 5 | 4 | 2 | 2 |
5 | 0 | 2 | 5 | 3 | 6 | 1 | 5 | 3 | 2 | 2 |
6 | 0 | 2 | 5 | 3 | 6 | 1 | 5 | 3 | 2 | 2 |
Из вершины 1 выходят дуги до вершин 2, 4, 5, 7, 8.
Считаем дуги длины не более 2:
![](686147_html_75744d1edb275cf1.png)
𝑑≤2(2) = min(10; 5 - 3) = 2
𝑑≤2(3) = min(∞; 10 + 3; 6 + 5) = 11
𝑑≤2(4) = min(8; 10 + 3; 5 – 2; 4 + 10) = 3
𝑑≤2(5) = min(6; 10 + 1; 8 + 10) = 6
𝑑≤2(6) = min(∞; 10 + 2; 8 – 2) = 6
𝑑≤2(7) = min(5; 8 + 5; 4 + 5) = 5
𝑑≤2(8) = min(4; 8 + 1) = 4
𝑑≤2(9) = min(∞; 10 + 8; 6 + 5) = 7
Обновились пути до вершин 2,3,4,9
Считаем дуги длины не более 3:
![](686147_html_d618cd513ebcd2e4.png)
𝑑≤3(3) = min(11; 2 + 3) = 5
𝑑≤3(4) = min(3; 2 + 3; 11 + 7) = 3
𝑑≤3(5) = min(6; 2 + 1; 11 + 4; 10 + 3; 11 + 5) = 6
𝑑≤3(6) = min(6; 2 + 2; 3 - 2) = 1
𝑑≤3(7) = min(5; 3 + 5) = 5
𝑑≤3(8) = min(4; 1 + 3; 11 + 1) = 4
𝑑≤3(9) = min(11; 8 + 2) = 10
𝑑≤3(10) = min(∞; 11 + 6) = 17
Обновился путь до вершин 3,6,9,10
Считаем дуги длины не более 4:
![](686147_html_72094a588d40776d.png)
𝑑≤4(2) = min(2; 1 + 8; 1 + 17) = 2
𝑑≤4(3) = min(5; 1 + 8) = 5
𝑑≤4(4) = min(3; 7 + 5; 3 + 17) = 3
𝑑≤4(5) = min(6; 4 + 5; 5 + 10) = 6
𝑑≤4(6) = min(1; 5 + 17) = 1
𝑑≤4(7) = min(5; 9 + 17) = 5
𝑑≤4(8) = min(4; 1 + 10) = 4
𝑑≤4(9) = min(10; 1 + 1; 5 + 17) = 2
𝑑≤4(10) = min(17; 6 + 5; 1 + 1) = 2
Обновился путь до вершин 9, 10
Считаем дуги длины не более 5:
![](686147_html_367483dedfe9c594.png)
𝑑≤5(2) = min(2; 2 + 1) = 2
𝑑≤5(4) = min(3; 3 + 2) = 3
𝑑≤5(5) = min(6; 5 + 2) = 6
𝑑≤5(6) = min(1; 5 + 2) = 1
𝑑≤5(7) = min(5; 9 + 2) = 5
𝑑≤5(8) = min(4; 1 + 2) = 3
𝑑≤5(9) = min(2; 5 + 2) = 2
Обновился путь до вершины 8
Считаем дуги длины не более 6:
![](686147_html_a1f78c19da806e70.png)
𝑑≤6(4) = min(3; 10 + 3) = 3
𝑑≤6(7) = min(5; 5 + 3) = 5
Ни один путь не изменился. Все кратчайшие пути найдены. Дерево кратчайших путей:
![](686147_html_b5db0e66d38f926b.png)
Список использованных источников
Гисин, В. Б. Дискретная математика : учебник и практикум для вузов / В. Б. Гисин. — Москва : Издательство Юрайт, 2021. — 383 с. — (Высшее образование). — ISBN 978-5-534-00228-7. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/468980 (дата обращения: 03.11.2021).
Палий, И. А. Дискретная математика и математическая логика : учебное пособие для вузов / И. А. Палий. — 3-е изд., испр. и доп. — Москва : Издательство Юрайт, 2021. — 370 с. — (Высшее образование). — ISBN 978- 5-534-12446-0. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/472909 (дата обращения: 03.11.2021).
Скорубский, В. И. Математическая логика : учебник и практикум для вузов / В. И. Скорубский, В. И. Поляков, А. Г. Зыков. — Москва : Издательство Юрайт, 2021. — 211 с. — (Высшее образование). — ISBN 978-5-534-01114-2.
— Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/469864 (дата обращения:03.11.2021).
Судоплатов, С. В. Дискретная математика : учебник и практикум для вузов / С. В. Судоплатов, Е. В. Овчинникова. — 5-е изд., испр. и доп. — Москва
: Издательство Юрайт, 2021. — 279 с. — (Высшее образование). — ISBN 978- 5-534-00871-5. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/468700 (дата обращения: 03.11.2021).
![](686147_html_e73e33aaded217c2.gif)