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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы на графах Тема лекции: Кратчайшие пути в графе. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 12 Лекция 12 Раздел: Алгоритмы на графах Тема лекции: Кратчайшие пути в графе (2)

Слайд 2

Описание слайда:

Расстояния между всеми парами вершин Найти расстояния d(s, t) :  s, t  V & (s  t ).

Слайд 3

Описание слайда:

Часть 1 лекции. Вспомогательная тема: Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)

Слайд 4

Описание слайда:

Пример

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Утверждение. Утверждение. Пусть A есть матрица смежности графа G. Элемент матрицы Ak равен числу путей длины k из вершины vi в вершину vj (vi V, vj V ).

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

Определение операции умножения и сложения булевских матриц

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

Алгоритм Уоршалла

Слайд 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}