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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Кратчайшие пути, слайд №1Кратчайшие пути, слайд №2Кратчайшие пути, слайд №3Кратчайшие пути, слайд №4Кратчайшие пути, слайд №5Кратчайшие пути, слайд №6Кратчайшие пути, слайд №7Кратчайшие пути, слайд №8Кратчайшие пути, слайд №9Кратчайшие пути, слайд №10Кратчайшие пути, слайд №11Кратчайшие пути, слайд №12Кратчайшие пути, слайд №13Кратчайшие пути, слайд №14Кратчайшие пути, слайд №15Кратчайшие пути, слайд №16Кратчайшие пути, слайд №17Кратчайшие пути, слайд №18
Скачать
Вы можете ознакомиться и скачать презентацию на тему Кратчайшие пути. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Задачи нахождения кратчайшего пути
Описание слайда:
Задачи нахождения кратчайшего пути

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


Варианты задач о кратчайшем пути Кратчайший путь из одной вершины: Дан взвешенный граф G=<V,E> и начальная вершина s. Требуется найти кратчайшие пути из s во все вершины vV Кратчайшие пути в одну вершину: Дана конечная вершина t. Требуется найти кратчайшие пути в t из всех вершин vV
Описание слайда:
Варианты задач о кратчайшем пути Кратчайший путь из одной вершины: Дан взвешенный граф G=<V,E> и начальная вершина s. Требуется найти кратчайшие пути из s во все вершины vV Кратчайшие пути в одну вершину: Дана конечная вершина t. Требуется найти кратчайшие пути в t из всех вершин vV

Слайд 6


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

Слайд 7


Варианты задач о кратчайшем пути Часто в задачах бывает необходимо найти не только кратчайший путь, но и сам путь. Для каждой вершины v будем помнить ее предшественников (v)
Описание слайда:
Варианты задач о кратчайшем пути Часто в задачах бывает необходимо найти не только кратчайший путь, но и сам путь. Для каждой вершины v будем помнить ее предшественников (v)

Слайд 8


Свойства кратчайших путей Лемма 1. (отрезки кратчайших путей являются кратчайшими) Пусть дан ориентированный взвешенный граф G=<V,E> с весовой функцией Если p(v1 , v2 ,…, vk) – кратчайший путь из v1 в vk и 1≤i≤j≤k, то pij=(vi , vi+1 , … , vj) – кратчайший путь из vi в vj
Описание слайда:
Свойства кратчайших путей Лемма 1. (отрезки кратчайших путей являются кратчайшими) Пусть дан ориентированный взвешенный граф G=<V,E> с весовой функцией Если p(v1 , v2 ,…, vk) – кратчайший путь из v1 в vk и 1≤i≤j≤k, то pij=(vi , vi+1 , … , vj) – кратчайший путь из vi в vj

Слайд 9


Свойства кратчайших путей Следствие 1 Пусть дан ориентированный взвешенный граф G=<V,E> с весовой функцией Рассмотрим кратчайший путь p из s в v. Пусть uv – последнее ребро этого пути. Тогда
Описание слайда:
Свойства кратчайших путей Следствие 1 Пусть дан ориентированный взвешенный граф G=<V,E> с весовой функцией Рассмотрим кратчайший путь p из s в v. Пусть uv – последнее ребро этого пути. Тогда

Слайд 10


Свойства кратчайших путей Лемма 2 Пусть дан ориентированный взвешенный граф G=<V,E> с весовой функцией Пусть sV Тогда для всякого ребра (u,v)E
Описание слайда:
Свойства кратчайших путей Лемма 2 Пусть дан ориентированный взвешенный граф G=<V,E> с весовой функцией Пусть sV Тогда для всякого ребра (u,v)E

Слайд 11


Релаксация Для каждого ребра vV будем хранить некоторое число d[v], являющееся верхней оценкой веса кратчайшего пути из вершины s в v (оценка кратчайшего пути)
Описание слайда:
Релаксация Для каждого ребра vV будем хранить некоторое число d[v], являющееся верхней оценкой веса кратчайшего пути из вершины s в v (оценка кратчайшего пути)

Слайд 12


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

Слайд 13


Релаксация Релаксация ребра (u, v) состоит в следующем: Значение d[v] уменьшается до d[u]+w(u,v), если второе значение меньше первого При этом (v)=u
Описание слайда:
Релаксация Релаксация ребра (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
Описание слайда:
Relax(u,v,w) If ( d[v]> d[u]+w(u,v)) d[v]=d[u]+w(u,v) [v]=u

Слайд 15


Алгоритм Дейкстры Решает задачу о кратчайших путях из одной вершины s графа G=<V,E> c весовой функцией w до всех остальных вершин графа. Веса всех ребер неотрицательны
Описание слайда:
Алгоритм Дейкстры Решает задачу о кратчайших путях из одной вершины s графа G=<V,E> c весовой функцией w до всех остальных вершин графа. Веса всех ребер неотрицательны

Слайд 16


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

Слайд 17


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

Слайд 18


Алгоритм Дейкстры Initialize(G,s) S=Ǿ Q=V[G] while Q<>Ǿ do u=min(Q) – выбираем вершину с наименьшим значением d[u] S=S U {u} for для всех вершин vAdj[u] do Relax(u,v,w)
Описание слайда:
Алгоритм Дейкстры Initialize(G,s) S=Ǿ Q=V[G] while Q<>Ǿ do u=min(Q) – выбираем вершину с наименьшим значением d[u] S=S U {u} for для всех вершин vAdj[u] do Relax(u,v,w)

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию