Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

Презентация на тему Кратчайшие пути

Содержание

2. ОпределенияПусть дан ориентированный взвешенный граф G= с
3. Определенияесли существует путь из u в v
4. ОпределенияКратчайший путь из u в v –
5. Варианты задач о кратчайшем путиКратчайший путь
6. Варианты задач о кратчайшем путиКратчайший путь
7. Варианты задач о кратчайшем путиЧасто в
8. Свойства кратчайших путейЛемма 1. (отрезки кратчайших путей
9. Свойства кратчайших путейСледствие 1 Пусть дан ориентированный
10. Свойства кратчайших путейЛемма 2 Пусть дан ориентированный
11. РелаксацияДля каждого ребра v∈V будем хранить некоторое
12. РелаксацияНачальное значение оценки кратчайшего пути и массива π определяется следующим образом:Initialize(G,s)
13. РелаксацияРелаксация ребра (u, v) состоит в следующем:Значение
14. Relax(u,v,w)If ( d[v]> d[u]+w(u,v)) d[v]=d[u]+w(u,v) π[v]=uВ вершинах указаны оценки кратчайшего пути
15. Алгоритм ДейкстрыРешает задачу о кратчайших путях из
16. Алгоритм ДейкстрыАлгоритм строит множество S вершин v,
17. Алгоритм ДейкстрыВершины, не лежащие в множестве S,
18. Скачать презентацию
19. Похожие презентации

ОпределенияПусть дан ориентированный взвешенный граф G= с весовой функцией Весом пути называется сумма весов ребер, входящих в этот путь:

Определенияесли существует путь из u в v

ОпределенияКратчайший путь из u в v – это любой путь p из

Варианты задач о кратчайшем путиКратчайший путь из одной вершины: Дан взвешенный

Варианты задач о кратчайшем путиКратчайший путь между парой вершин: Даны вершины

Варианты задач о кратчайшем путиЧасто в задачах бывает необходимо найти не

Свойства кратчайших путейЛемма 1. (отрезки кратчайших путей являются кратчайшими) Пусть дан ориентированный

Свойства кратчайших путейСледствие 1 Пусть дан ориентированный взвешенный граф G= с

Свойства кратчайших путейЛемма 2 Пусть дан ориентированный взвешенный граф G= с

РелаксацияДля каждого ребра v∈V будем хранить некоторое число d[v], являющееся верхней оценкой

РелаксацияНачальное значение оценки кратчайшего пути и массива π определяется следующим образом:Initialize(G,s)

РелаксацияРелаксация ребра (u, v) состоит в следующем:Значение d[v] уменьшается до d[u]+w(u,v),

Relax(u,v,w)If ( d[v]> d[u]+w(u,v)) d[v]=d[u]+w(u,v) π[v]=uВ вершинах указаны оценки кратчайшего пути

Алгоритм ДейкстрыРешает задачу о кратчайших путях из одной вершины s графа G=

Алгоритм ДейкстрыАлгоритм строит множество S вершин v, для которых кратчайшие пути до

Алгоритм ДейкстрыВершины, не лежащие в множестве S, хранятся в очереди с приоритетами,

Алгоритм ДейкстрыInitialize(G,s) S=Ǿ Q=V[G] while QǾ do u=min(Q) – выбираем вершину с наименьшим значением d[u] S=S

Слайды презентации

Слайд 2 Определения
Пусть дан ориентированный взвешенный граф G=
с весовой

функцией
Весом пути
называется сумма весов ребер, входящих

в этот путь:

Слайд 3 Определения
если существует путь из u в v

Слайд 4 Определения
Кратчайший путь из u в v – это

ОпределенияКратчайший путь из u в v – это любой путь p

любой путь p из u и v, для
которого

Слайд 5 Варианты задач о кратчайшем пути
Кратчайший путь из одной

вершины: Дан взвешенный граф G= и начальная вершина s. Требуется найти кратчайшие

пути из s во все вершины v∈V
Кратчайшие пути в одну вершину: Дана конечная вершина t. Требуется найти кратчайшие пути в t из всех вершин v∈V

Слайд 6 Варианты задач о кратчайшем пути
Кратчайший путь между парой

вершин: Даны вершины u и v. Требуется найти кратчайший путь из

u в v
Кратчайшие пути для всех пар вершин: Для каждой пары вершин u и v найти кратчайший путь из u в v

Слайд 7 Варианты задач о кратчайшем пути
Часто в задачах бывает

необходимо найти не только кратчайший путь, но и сам

путь.
Для каждой вершины v будем помнить ее предшественников π(v)

Слайд 8 Свойства кратчайших путей
Лемма 1. (отрезки кратчайших путей являются

Свойства кратчайших путейЛемма 1. (отрезки кратчайших путей являются кратчайшими) Пусть дан

кратчайшими) Пусть дан ориентированный взвешенный граф G=
с весовой

функцией
Если p(v1 , v2 ,…, vk) –
кратчайший путь из v1 в vk и 1≤i≤j≤k, то
pij=(vi , vi+1 , … , vj) –
кратчайший путь из vi в vj

Слайд 9 Свойства кратчайших путей
Следствие 1 Пусть дан ориентированный взвешенный граф

G=
с весовой функцией
Рассмотрим кратчайший путь

p из s в v.
Пусть u→v – последнее ребро этого пути. Тогда

Слайд 10 Свойства кратчайших путей
Лемма 2 Пусть дан ориентированный взвешенный граф

G=
с весовой функцией
Пусть s∈V

Тогда для всякого ребра (u,v)∈E

Слайд 11 Релаксация
Для каждого ребра v∈V будем хранить некоторое число

РелаксацияДля каждого ребра v∈V будем хранить некоторое число d[v], являющееся верхней

d[v], являющееся верхней оценкой веса кратчайшего пути из вершины

s в v (оценка кратчайшего пути)

Слайд 12 Релаксация
Начальное значение оценки кратчайшего пути и массива π

определяется следующим образом:
Initialize(G,s)

Слайд 13 Релаксация
Релаксация ребра (u, v) состоит в следующем:
Значение d[v]

РелаксацияРелаксация ребра (u, v) состоит в следующем:Значение d[v] уменьшается до

уменьшается до
d[u]+w(u,v), если
второе значение меньше первого
При

этом π(v)=u

Слайд 14 Relax(u,v,w)
If ( d[v]> d[u]+w(u,v)) d[v]=d[u]+w(u,v)
π[v]=u
В вершинах указаны

оценки кратчайшего пути

Слайд 15 Алгоритм Дейкстры
Решает задачу о кратчайших путях из одной

Алгоритм ДейкстрыРешает задачу о кратчайших путях из одной вершины s графа

вершины s графа G= c весовой функцией w до

всех остальных вершин графа.
Веса всех ребер неотрицательны

Слайд 16 Алгоритм Дейкстры
Алгоритм строит множество S вершин v, для

Алгоритм ДейкстрыАлгоритм строит множество S вершин v, для которых кратчайшие пути

которых кратчайшие пути до вершины s уже известны, т.е.

d[v]=δ(s,v)
На каждом шаге к множеству S добавляется та из оставшихся вершин u, для которой d[u] имеет наименьшее значение
После этого проводится релаксация всех ребер, выходящих из u