Кратчайшие пути

Сентябрь 7, 2022

Главная
Алгебра
Кратчайшие пути

Содержание

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

Слайд 2

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

называется сумма весов ребер, входящих в этот путь:

Слайд 3

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

Слайд 4

Определения
Кратчайший путь из u в v – это
любой путь 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. (отрезки кратчайших путей являются кратчайшими) Пусть дан ориентированный

взвешенный граф 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 будем хранить некоторое число d[v], являющееся верхней

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

Слайд 12

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

Слайд 13

Релаксация
Релаксация ребра (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 графа

G= c весовой функцией w до всех остальных вершин графа.
Веса всех ребер неотрицательны

Слайд 16

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

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

Слайд 17

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

приоритетами, определяемыми значениями функции d.
Пусть граф представлен списками смежности Adj[u] –список смежных вершин u
Q – очередь с приоритетами

Кратчайшие пути

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие презентации