Кратчайшие пути в графе - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

Кратчайшие пути в графе Путь p в графе G = (V, E): p: u  v  u = u1  u2  u3  …  uk = v Взвешенный граф G = (V, E, W), где w(i, j) = w(vi, vj) - произвольны. Длина пути:

Слайд 3

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

Вычисление расстояний и нахождение путей Пусть вычислены все расстояния d (u, v), в т.ч. d (s, t). Как найти путь p: s  t ?

Слайд 4

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

Пример

Слайд 5

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

Пример

Слайд 6

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

Алгоритм нахождения кратчайшего пути по расстояниям между вершинами /*Дано: s, t – фиксированные вершины; s, t V; DL [ * ] – расстояния от вершины s до каждой вершины графа; DL[v]=d(s,v); W[u, v] – матрица весов ребер, u, v V; Результат: St – стек, содержащий кратчайший путь от s до t, т.е. последовательность вершин s=v0, v1, … , vk=t */ Create(st); st  t; v = t; while (v != s) { u = вершина, для которой DL[v]=DL[u]+W[u,v]; St  u; v=u; }

Слайд 7

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

Алгоритм нахождения кратчайшего пути продолжение Детализация строки u = вершина, для которой DL[v]=DL[u]+W[u,v];

Слайд 8

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

Задачи вычисления длин кратчайших путей (расстояний) Стартовая вершина s фиксирована, конечная вершина t фиксирована. Найти d (s, t). Стартовая вершина s фиксирована. Найти d (s, v) для  v  V \ s. Найти d (s, t) :  s, t  V & (s  t ). Т.е. найти расстояния между всеми парами вершин. Замечание: неизвестен ни один алгоритм решения задачи 1, который был бы более эффективным, чем известные алгоритмы, решающие задачу 2

Слайд 9

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

Слайд 10

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

Релаксация (ослабление) ребра u  v

Слайд 11

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

Релаксация входящих ребер относительно вершины v : Релаксация входящих ребер относительно вершины v : for (u  Adj_In[v]) Relax(u, v); В результате dl [v] = min ( dl [u] + W [ u, v ]  u  Adj_In[v] ) Инициализация: dl [v] = W [ s, v ] или dl [v] = , dl [s] = 0. Утверждение 1. Если dl [v] = d (s, v), то релаксация не изменит dl [v] . Утверждение 2. Если u лежит на кратчайшем пути s  v и dl [u] = d (s, u), то после Relax(u, v) будет dl [v] = d (s, v).

Слайд 12

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

Продолжение на лекции 5 мая

Слайд 13

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

Слайд 14

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

Алгоритм Дейкстры (Dijkstra E.W. - 1959)

Слайд 15

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

Алгоритм Дейкстры W [ *, * ]  0 Идея алгоритма: V = S + T, S  T=  Инвариант: (  vS : DL[v] = d(s,v) ) & (  vT : DL[v] = длина кратчайшего из тех путей из s в v, в которых все вершины, кроме v, принадлежат множеству S )

Слайд 16

$for ( v V) DL[v] =W[s,v]; DL[s] =0; T = V \ {s}; // S = {{s}} while (T  ) { u = вершина xT, такая, что DL[x] = min { DL[p] : p T }; T =T \ {u};...$

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

for ( v V) DL[v] =W[s,v]; DL[s] =0; T = V \ {s}; // S = {{s}} while (T  ) { u = вершина xT, такая, что DL[x] = min { DL[p] : p T }; T =T \ {u}; // S =S+{u} for ( v T) Relax (u,v); } //while

Слайд 17

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

Пример

Слайд 18

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

Пример

Слайд 19

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

Корректность алгоритма: см. инвариант цикла while; Корректность алгоритма: см. инвариант цикла while; от противного

Слайд 20

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

1) Множество T представляется 1) Множество T представляется пирамидой Heap(T) с приоритетами DL[v]; при этом Inv Heap(T): (uT: (u=отец (v))  (DL[u]  DL[v]) ). Тогда min(T) – в корне Heap(T), и исключение u из T есть удаление корня Heap(T) с восстановлением пирамидальности. 2) Используются списки смежности AdjOut[*]. Тогда обновление DL[v] после выбора вершины u реализуется следующим образом: for (v AdjOut[u]) if (DL[u] + W[u,v] < DL[v]) { DL[v] = DL[u]+W[u,v]; Восстановить пирамидальность Heap(T) вверх от узла v; }

Слайд 21

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

Следующий Алгоритм Форда-Беллмана

Слайд 22

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

Алгоритм Форда-Беллмана Алгоритм Форда-Беллмана нахождения расстояний от источника до остальных вершин в графе, не содержащем контуров отрицательной длины Дано: Орграф G= с выделенным источником sV; V = n ; W[u, v] – матрица весов дуг, u, v V; (граф не содержит контуров отрицательной длины) Результат: Расстояния от источника s до всех вершин графа DL[v] = d(s,v), v V;

Слайд 23

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

Алгоритм Форда-Беллмана Пример непригодности алгоритма Дейкстры при произвольных весах

Слайд 24

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

for ( v  V) DL[v] =W[s,v]; for ( v  V) DL[v] =W[s,v]; DL[s] = 0; for (k=1; k

Слайд 25

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

Вариант сложности O (nm) Вариант сложности O (nm) for ( v  V) DL[v]=W[s,v]; DL[s] =0; for (k=1; k

Слайд 26

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

Пример. n = 6 Шаг 0

Слайд 27

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

Пример. n = 6 Шаг 1

Слайд 28

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

Пример. n = 6 Шаг 2

Слайд 29

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

Пример. n = 6 Шаг 3

Слайд 30

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

Индуктивное утверждение (“инвариант”) цикла Индуктивное утверждение (“инвариант”) цикла for (k=1; k

Слайд 31

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

Если P( [1..k) ) и P( [1..k] ) действительно инварианты, то для остановки необходимо, чтобы после k итераций было бы k + 1 = n  1 (т.к. путь без циклов в графе с n вершинами может иметь не более n  1 дуг ). Если P( [1..k) ) и P( [1..k] ) действительно инварианты, то для остановки необходимо, чтобы после k итераций было бы k + 1 = n  1 (т.к. путь без циклов в графе с n вершинами может иметь не более n  1 дуг ). Отсюда k = n  2 Покажем, что действительно тело внешнего цикла переводит P( [1..k) ) в P( [1..k] )

Слайд 32

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

После очередной итерации После очередной итерации d(s,v)  DL[v]  { по алгоритму, с учетом того, что пометки DL[u] могли уже уменьшиться на предыдущих шагах циклов внутри одной итерации по k }  min {DL[u] + W[u,v]  u  V }   min {d[ k | u ] + W[u,v]  u  V } = d[ k + 1 | u ]