Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Алгоритмы на графах Тема лекции: Кратчайшие пути в графе
Содержание
- 1. Алгоритмы на графах Тема лекции: Кратчайшие пути в графе
- 2. 07.05.2013Кратчайшие пути 2Расстояния между всеми парами вершинНайти
- 3. 07.05.2013Кратчайшие пути 2Часть 1 лекции. Вспомогательная тема:Транзитивное
- 4. 07.05.2013Кратчайшие пути 2Пример
- 5. 07.05.2013Кратчайшие пути 2Матрица путейМатрица путей (или матрица
- 6. 07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 1
- 7. 07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 2
- 8. 07.05.2013Кратчайшие пути 2Утверждение. Пусть A есть матрица
- 9. 07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 3
- 10. 07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 4
- 11. 07.05.2013Кратчайшие пути 2Степени матрицы смежностиПути длины 5
- 12. 07.05.2013Кратчайшие пути 2Степени матрицы смежностиТ.к. перемножение матриц
- 13. 07.05.2013Кратчайшие пути 2Определение операции умножения и сложения булевских матриц O(n3log n),
- 14. 07.05.2013Кратчайшие пути 2Далее Алгоритм Уоршалла (Warshall)См. далее текстовый файл «Лекция 12 Кратч пути (2) 05-05-2014.doc»
- 15. Алгоритм Уоршалла (Warshall)Пусть вершины графа пронумерованы числами
- 16. Алгоритм Уоршалла07.05.2013Кратчайшие пути 2
- 17. {Инициализация: }{1} for i := 1 to n do{2} for j := 1
- 18. 07.05.2013Кратчайшие пути 2КОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ
- 19. Скачать презентанцию
07.05.2013Кратчайшие пути 2Расстояния между всеми парами вершинНайти расстояния d(s, t) : ∀ s, t ∈ V & (s ≠ t ).
Слайды и текст этой презентации
Слайд 107.05.2013
Кратчайшие пути 2
Лекция 12
Раздел: Алгоритмы на графах
Тема лекции:
Кратчайшие пути
в графе (2)
Слайд 207.05.2013
Кратчайшие пути 2
Расстояния между всеми парами вершин
Найти расстояния d(s, t)
: ∀ s, t ∈ V & (s ≠ t
).
Слайд 307.05.2013
Кратчайшие пути 2
Часть 1 лекции. Вспомогательная тема:
Транзитивное замыкание графа.
Алгоритм
Уоршалла (Warshall)
Задан ориентированный граф G = (V, E).
Транзитивное замыкание графа G есть
граф G*, состоящий из тех же вершин, т.е. G* = (V, E* ), а множество рёбер E* естьE * = {(u, v): (u ∈ V) & (u ∈ V) &
& (существует путь из u в v в графе G) }.
Слайд 507.05.2013
Кратчайшие пути 2
Матрица путей
Матрица путей (или матрица достижимости) P графа
G :
pij = 1, если существует путь из вершины в вершину
в графе G, и pij = 0 в противном случае.
Матрица путей P графа G совпадает с матрицей смежности А* его транзитивного замыкания G*.
Слайд 807.05.2013
Кратчайшие пути 2
Утверждение.
Пусть A есть матрица смежности графа G.
Элемент
матрицы Akравен числу путей длины k из вершины vi в вершину vj (vi ∈V, vj ∈V ).
Степени матрицы смежности
Слайд 1207.05.2013
Кратчайшие пути 2
Степени матрицы смежности
Т.к. перемножение матриц осуществляется за время
O(n3),
то вычислить матрицу P можно за O(n⋅n3) = O(n4) операций.
Слайд 1307.05.2013
Кратчайшие пути 2
Определение операции умножения и сложения булевских матриц
O(n3log n),
Слайд 1407.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
Слайд 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»
Слайд 1807.05.2013
Кратчайшие пути 2
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ
ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
