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

Алгоритмы на графах
1/31
Средняя оценка: 4.5/5 (всего оценок: 81)
Скачать (1005 Кб)
Код скопирован в буфер обмена
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

3

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

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

4

Слайд 4

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

5

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

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

6

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

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

7

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

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

8

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

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

9

Слайд 9

10

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

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

11

Слайд 11

12

Слайд 12

13

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

14

Слайд 14

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

15

Слайд 15

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

16

Слайд 16

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

17

Слайд 17

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

18

Слайд 18

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

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.

20

Слайд 20

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

21

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

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

22

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

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

23

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

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

24

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

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

25

Слайд 25

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

26

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

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

27

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

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

28

Слайд 28

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

29

Слайд 29

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

30

Слайд 30

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

31

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

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

Ничего не найдено