Алгоритмы на графах Тема лекции: Кратчайшие пути в графе

Сентябрь 3, 2022

Главная
Алгебра
Алгоритмы на графах Тема лекции: Кратчайшие пути в графе

Содержание

2. 07.05.2013 Кратчайшие пути 2 Расстояния между всеми парами вершин Найти расстояния d(s, t) : ∀ s,
3. 07.05.2013 Кратчайшие пути 2 Часть 1 лекции. Вспомогательная тема: Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall) Задан
4. 07.05.2013 Кратчайшие пути 2 Пример
5. 07.05.2013 Кратчайшие пути 2 Матрица путей Матрица путей (или матрица достижимости) P графа G : pij
6. 07.05.2013 Кратчайшие пути 2 Степени матрицы смежности Пути длины 1
7. 07.05.2013 Кратчайшие пути 2 Степени матрицы смежности Пути длины 2
8. 07.05.2013 Кратчайшие пути 2 Утверждение. Пусть A есть матрица смежности графа G. Элемент матрицы Ak равен
9. 07.05.2013 Кратчайшие пути 2 Степени матрицы смежности Пути длины 3
10. 07.05.2013 Кратчайшие пути 2 Степени матрицы смежности Пути длины 4
11. 07.05.2013 Кратчайшие пути 2 Степени матрицы смежности Пути длины 5
12. 07.05.2013 Кратчайшие пути 2 Степени матрицы смежности Т.к. перемножение матриц осуществляется за время O(n3), то вычислить
13. 07.05.2013 Кратчайшие пути 2 Определение операции умножения и сложения булевских матриц O(n3log n),
14. 07.05.2013 Кратчайшие пути 2 Далее Алгоритм Уоршалла (Warshall) См. далее текстовый файл «Лекция 12 Кратч пути
15. Алгоритм Уоршалла (Warshall) Пусть вершины графа пронумерованы числами от 1 до n. Нас будут интересовать пути,
16. Алгоритм Уоршалла 07.05.2013 Кратчайшие пути 2
17. {Инициализация: } {1} for i := 1 to n do {2} for j := 1 to
19. Скачать презентацию

Слайд 2

07.05.2013
Кратчайшие пути 2
Расстояния между всеми парами вершин
Найти расстояния d(s, t) :

∀ s, t ∈ V & (s ≠ t ).

Слайд 3

07.05.2013
Кратчайшие пути 2
Часть 1 лекции. Вспомогательная тема:
Транзитивное замыкание графа.
Алгоритм Уоршалла

(Warshall)

Задан ориентированный граф G = (V, E).
Транзитивное замыкание графа G есть граф G*, состоящий из тех же вершин, т.е. G* = (V, E* ), а множество рёбер E* есть
E * = {(u, v): (u ∈ V) & (u ∈ V) &
& (существует путь из u в v в графе G) }.

Слайд 4

07.05.2013
Кратчайшие пути 2
Пример

Слайд 5

07.05.2013
Кратчайшие пути 2
Матрица путей
Матрица путей (или матрица достижимости) P графа G

:
pij = 1, если существует путь из вершины в вершину в графе G, и
pij = 0 в противном случае.
Матрица путей P графа G совпадает с матрицей смежности А* его транзитивного замыкания G*.

Слайд 6

07.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Пути длины 1

Слайд 7

07.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Пути длины 2

Слайд 8

07.05.2013
Кратчайшие пути 2
Утверждение.
Пусть A есть матрица смежности графа G.
Элемент

матрицы Ak
равен числу путей длины k из вершины vi в вершину vj (vi ∈V, vj ∈V ).

Степени матрицы смежности

Слайд 9

07.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Пути длины 3

Слайд 10

07.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Пути длины 4

Слайд 11

07.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Пути длины 5

Слайд 12

07.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Т.к. перемножение матриц осуществляется за время O(n3),

то вычислить матрицу P можно за O(n⋅n3) = O(n4) операций.

Слайд 13

07.05.2013
Кратчайшие пути 2
Определение операции умножения и сложения булевских матриц
O(n3log n),

Слайд 14

07.05.2013
Кратчайшие пути 2
Далее Алгоритм Уоршалла (Warshall)
См. далее текстовый файл
«Лекция 12

Кратч пути (2) 05-05-2014.doc»

Слайд 15

Алгоритм Уоршалла (Warshall)
Пусть вершины графа пронумерованы числами от 1 до n.

Нас будут интересовать пути, проходящие через промежуточные вершины из некоторого определенного множества.
Определим булевские величины bij(k)
bij(k)= (∃ путь из вершины i в вершину j , проходящий через промежуточные вершины только из множества вершин с номерами от 1 до k)

07.05.2013

Кратчайшие пути 2

Слайд 16

Алгоритм Уоршалла
07.05.2013
Кратчайшие пути 2

Слайд 17

{Инициализация: }
{1} for i := 1 to n do
{2} for j := 1 to n do
{3} if i = j

then else ;
{4} for k := 1 to n do
{5} for i := 1 to n do
{6} for j := 1 to n do
{7}

07.05.2013

Кратчайшие пути 2

Далее см. файл«Лекция 12 Кратч пути (2) 05-05-2014.doc»

Алгоритмы на графах Тема лекции: Кратчайшие пути в графе

Содержание

07.05.2013Кратчайшие пути 2Расстояния между всеми парами вершинНайти расстояния d(s, t) :

07.05.2013Кратчайшие пути 2Часть 1 лекции. Вспомогательная тема:Транзитивное замыкание графа. Алгоритм Уоршалла

07.05.2013Кратчайшие пути 2Пример

07.05.2013Кратчайшие пути 2Матрица путейМатрица путей (или матрица достижимости) P графа G

07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 1

07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 2

07.05.2013Кратчайшие пути 2Утверждение. Пусть A есть матрица смежности графа G. Элемент

07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 3

07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 4

07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 5

07.05.2013Кратчайшие пути 2Степени матрицы смежностиТ.к. перемножение матриц осуществляется за время O(n3),

07.05.2013Кратчайшие пути 2Определение операции умножения и сложения булевских матриц O(n3log n),

07.05.2013Кратчайшие пути 2Далее Алгоритм Уоршалла (Warshall)См. далее текстовый файл «Лекция 12

Алгоритм Уоршалла (Warshall)Пусть вершины графа пронумерованы числами от 1 до n.

Алгоритм Уоршалла07.05.2013Кратчайшие пути 2

{Инициализация: }{1} for i := 1 to n do{2} for j := 1 to n do{3} if i = j

Похожие презентации