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

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

Определения

Слайд 4

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

Определения

Слайд 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 – очередь с приоритетами

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

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

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