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

Смотреть слайды в полном размере
Презентация «Алгоритмы на графах Тема лекции: Кратчайшие пути в графе»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 18 слайдов и доступен в формате ppt. Размер файла: 511.50 KB

Просмотреть и скачать

Pic.1
Лекция 12 Лекция 12 Раздел: Алгоритмы на графах Тема лекции: Кратчайшие пути в графе (2)
Лекция 12 Лекция 12 Раздел: Алгоритмы на графах Тема лекции: Кратчайшие пути в графе (2)
Pic.2
Расстояния между всеми парами вершин Найти расстояния d(s, t) :  s, t  V & (s  t ).
Расстояния между всеми парами вершин Найти расстояния d(s, t) :  s, t  V & (s  t ).
Pic.3
Часть 1 лекции. Вспомогательная тема: Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)
Часть 1 лекции. Вспомогательная тема: Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)
Pic.4
Пример
Пример
Pic.5
Матрица путей Матрица путей (или матрица достижимости) P графа G : pij = 1, если существует путь из
Матрица путей Матрица путей (или матрица достижимости) P графа G : pij = 1, если существует путь из вершины в вершину в графе G, и pij = 0 в противном случае. Матрица путей P графа G совпадает с …
Pic.6
Степени матрицы смежности
Степени матрицы смежности
Pic.7
Степени матрицы смежности
Степени матрицы смежности
Pic.8
Утверждение. Утверждение. Пусть A есть матрица смежности графа G. Элемент матрицы Ak равен числу пут
Утверждение. Утверждение. Пусть A есть матрица смежности графа G. Элемент матрицы Ak равен числу путей длины k из вершины vi в вершину vj (vi V, vj V ).
Pic.9
«Алгоритмы на графах Тема лекции: Кратчайшие пути в графе», слайд 9
Pic.10
«Алгоритмы на графах Тема лекции: Кратчайшие пути в графе», слайд 10
Pic.11
«Алгоритмы на графах Тема лекции: Кратчайшие пути в графе», слайд 11
Pic.12
«Алгоритмы на графах Тема лекции: Кратчайшие пути в графе», слайд 12
Pic.13
Определение операции умножения и сложения булевских матриц
Определение операции умножения и сложения булевских матриц
Pic.14
Далее Алгоритм Уоршалла (Warshall) См. далее текстовый файл «Лекция 12 Кратч пути (2) 05-05-2014. do
Далее Алгоритм Уоршалла (Warshall) См. далее текстовый файл «Лекция 12 Кратч пути (2) 05-05-2014. doc»
Pic.15
Алгоритм Уоршалла (Warshall) Пусть вершины графа пронумерованы числами от 1 до n. Нас будут интересо
Алгоритм Уоршалла (Warshall) Пусть вершины графа пронумерованы числами от 1 до n. Нас будут интересовать пути, проходящие через промежуточные вершины из некоторого определенного множества. Определим …
Pic.16
Алгоритм Уоршалла
Алгоритм Уоршалла
Pic.17
{Инициализация: } {Инициализация: } {1} for i := 1 to n do {2} for j := 1 to n do {3} if i = j then
{Инициализация: } {Инициализация: } {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}
Pic.18
КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!