Презентация на тему: Алгоритмы на графах

Реклама. Продолжение ниже
Алгоритмы на графах
Алгоритмы на графах
Основные алгоритмы
Алгоритмы на графах
Алгоритм Дейкстры
Алгоритм Дейкстры
Формулировка задачи
Алгоритм
Алгоритмы на графах
Шаг алгоритма
Алгоритмы на графах
Алгоритмы на графах
пример поиска кратчайшего пути на графе ( алгоритм Дейкстры )
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
Алгоритм Крускала ( Краскала )
Минимальное остовное дерево
Формулировка задачи
Шаги алгоритма
Алгоритмы на графах
Пример работы алгоритма Крускала
Пример работы алгоритма Крускала
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
Алгоритмы на графах
1/31
Средняя оценка: 4.5/5 (всего оценок: 81)
Код скопирован в буфер обмена
Скачать (1005 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Алгоритмы на графах

Изображение слайда
1/1
2

Слайд 2

Алгоритм Объект работы Действие Сложность Доп. память Полезн. Матрица Список Поиск в ширину Невзвеш-й граф Поиск кратчайшего расстояния от одной вершины до всех остальных, определение количества компонент связности, определение двудольности графа O(N 2 ) O(M) O(N) 10 Поиск в глубину Невзвеш-й граф Определение количества компонент связности, построение дерева поиска в глубину, поиск точек сочленения и мостов, определение двудольности графа O(N 2 ) O(M) O(N) 8 Алгоритм Дейкстры Взвеш-й граф без рёбер отрицат-го веса Поиск кратчайшего расстояния от одной вершины до всех остальных O(N 2 ) O(N 2 ), O(N) 10 Алгоритм Форда-Беллмана Взвешенный граф Поиск кратчайшего расстояния от одной вершины до всех остальных O(N 3 ) O(MN) O(N) 5 Алгоритм Флойда Взвешенный граф Поиск кратчайшего расстояния между каждой парой вершин O(N 3 ) O(N 2 ) 8

Изображение слайда
1/1
3

Слайд 3: Основные алгоритмы

Нахождение кратчайших путей из одного источника: алгоритм Дейкстры. Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе.

Изображение слайда
1/1
4

Слайд 4

Алгоритм Дейкстры

Изображение слайда
1/1
5

Слайд 5: Алгоритм Дейкстры

Э́дсгер Ви́бе Де́йкстра   ( Edsger Wybe Dijkstra  [ˈ ɛtsxər ˈ ʋibə ˈ dɛikstra ] ) (11 мая 1930, Роттердам, Нидерланды — 6 августа  2002)  — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии.

Изображение слайда
Изображение для работы со слайдом
1/2
6

Слайд 6: Алгоритм Дейкстры

Алгоритм Дейкстры   — алгоритм на графах, изобретённый нидерландским ученым Э.Дейкстрой  в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Изображение слайда
1/1
7

Слайд 7: Формулировка задачи

Дан взвешенный ориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины а до всех остальных вершин этого графа Граф называется  взвешенным  или  нагруженным, если каждому ребру поставлено в соответствии некоторое число   w  (вес).

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
8

Слайд 8: Алгоритм

Каждой вершине из  V  сопоставим метку — минимальное известное расстояние от этой вершины до  а. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены. Метка самой вершины  а  полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от  a  до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
9

Слайд 9

Изображение слайда
Изображение для работы со слайдом
1/2
10

Слайд 10: Шаг алгоритма

Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина  u, имеющая минимальную метку. Рассматриваем всевозможные маршруты из u. Вершины, в которые ведут рёбра из  u, называются   соседями  этой вершины. Для каждого соседа вершины  u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки  u  и длины ребра, соединяющего  u  с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину  u  как посещенную и повторим шаг алгоритма.

Изображение слайда
1/1
11

Слайд 11

Изображение слайда
Изображение для работы со слайдом
1/2
12

Слайд 12

Изображение слайда
Изображение для работы со слайдом
1/2
13

Слайд 13: пример поиска кратчайшего пути на графе ( алгоритм Дейкстры )

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
14

Слайд 14

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

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
Реклама. Продолжение ниже
15

Слайд 15

Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.

Изображение слайда
Изображение для работы со слайдом
1/2
16

Слайд 16

Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
17

Слайд 17

Задача. Для н-графа найти длины кратчайших путей от вершины 1 ко всем остальным вершинам и восстановить кратчайшие пути к ним. d(1,2)=7 d(1,3)=9 d(1,4)=20 d(1,5)=20 d(1,6)=11

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
18

Слайд 18

Код программы алгоритма Дейкстры на Pascal:

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
19

Слайд 19

program  DijkstraAlgorithm ; uses  crt ; const  V=6; inf =100000; type  vektor =array[1..V] of integer; var  start: integer; const  GR: array[1..V, 1..V] of integer=( (0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); {_________________________________________________________________} procedure  Dijkstra (GR: array[1..V, 1..V] of integer; st : integer); var  count, index,  i, u, m, min: integer; distance:  vektor ; visited: array[1..V] of  boolean ; begin m:=st; for i:=1 to V do begin distance[ i ]:= inf ; visited[ i ]:=false; end; distance[ st ]:=0; for count:=1 to V-1 do begin min:= inf ; for i:=1 to V do if (not visited[ i ]) and (distance[ i ]<=min) then begin min:=distance[ i ]; index:= i ; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[ i ]) and (GR[u,  i ]<>0) and (distance[u]<> inf ) and (distance[u]+GR[u,  i ]<distance[ i ]) then distance[ i ]:=distance[u]+GR[u,  i ]; end; write(' Стоимость пути из начальной вершины до остальных:');  writeln ; for i:=1 to V do if distance[ i ]<> inf  then writeln (m,' > ',  i,' = ', distance[ i ]) else  writeln (m,' > ',  i,' = ', ' маршрут недоступен'); end; { главное тело программы} begin clrscr ; write(' Начальная вершина >> ');  read(start); Dijkstra (GR, start); end.

Изображение слайда
1/1
20

Слайд 20

Алгоритм Крускала

Изображение слайда
1/1
21

Слайд 21: Алгоритм Крускала ( Краскала )

Крускал, Джозеф Б.    ( Kruskal, Joseph B. ) 29. 01. 1928 –19. 09. 2010 Почетный профессор.  Bell Labs,   Lucent Technologies, Room 2C-281, Murray Hill, NJ 07974, USA Алгоритм Крускала  (или  алгоритм Краскала ) — алгоритм построения минимального остовного дерева взвешенного графа. Алгоритм впервые описан Джозефом Крускалом  в 1956 году.

Изображение слайда
Изображение для работы со слайдом
1/2
22

Слайд 22: Минимальное остовное дерево

Пример связного графа и двух его остовных деревьев Минимальным остовным деревом называется остовное дерево с минимальным общим весом его ребер. 2 3 5 2 1 4 3 6 2

Изображение слайда
Изображение для работы со слайдом
1/2
23

Слайд 23: Формулировка задачи

Для связного взвешенного графа   G=(V,E) построить минимальный остов  S=(V,T). Вход :  связный граф  G=(V,E) и  функция  стоимости (весов) ребер c: E -> R. Выход :  минимальный остов  S=(V,T). Формулировка задачи

Изображение слайда
1/1
24

Слайд 24: Шаги алгоритма

Создается список ребер E, содержащий длину ребра, номер исходной вершины ребра, номер конечной вершины ребра. Данный список упорядочивается в порядке возрастания длин ребер. Просматривается список E и выбирается из него ребро с минимальной длиной, еще не включенное в результирующее дерево S и не образующее цикла с уже построенными ребрами. Если все вершины графа включены в дерево S и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Изображение слайда
1/1
25

Слайд 25

Пусть E содержит  m  ребер. Упорядочим их  по  возрастанию стоимостей: Последовательно для каждого  i =1,..., m  определим множество ребер  T i : Положим  T=T m. Выдать в качестве результата  граф  S=(V,T). Шаги алгоритма

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
26

Слайд 26: Пример работы алгоритма Крускала

Исходный граф Минимальный остов графа минимальный остов   S=(V,T), где  T=T 8  ={ ( a,g ), ( g,e ), ( g,c ), ( e,d ), ( a,b ), ( f,g )}

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
27

Слайд 27: Пример работы алгоритма Крускала

Найти минимальный остов неориентированного взвешенного графа. Пример работы алгоритма Крускала Д/З Найти минимальный остов неориентированного взвешенного графа.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
28

Слайд 28

Исходный граф Минимальное остовное дерево Исходный граф Минимальное остовное дерево Задача. Найти минимальный остов неориентированного взвешенного графа.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
29

Слайд 29

Найти минимальный остов взвешенного графа Найти минимальное расстояние от вершины v3 до остальных вершин Вариант 1 Найти минимальное расстояние от вершины 6 до остальных вершин Найти минимальный остов взвешенного графа Вариант 2

Изображение слайда
1/1
30

Слайд 30

Вариант 1 Вариант 2 6 4 3

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/5
31

Последний слайд презентации: Алгоритмы на графах

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже