Презентация на тему: Структуры и алгоритмы обработки данных на ЭВМ Алгоритм Дейкстры

Структуры и алгоритмы обработки данных на ЭВМ Алгоритм Дейкстры Введение Задачи Последовательность шагов Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Нахождение кратчайшего пути в неориентированном графе Результаты работы алгоритма Структуры и алгоритмы обработки данных на ЭВМ Алгоритм Дейкстры
1/28
Средняя оценка: 4.4/5 (всего оценок: 94)
Скачать (369 Кб)
Код скопирован в буфер обмена
1

Первый слайд презентации: Структуры и алгоритмы обработки данных на ЭВМ Алгоритм Дейкстры

Красиков И.А. ТУСУР 2015

2

Слайд 2: Введение

Э́дсгер Ви́бе Де́йкстра  (11.05.1930— 6.08.2002) — нидерландский учёный, труды которого оказали влияние на развитие информатики и информационных технологий, является одним из разработчиков концепции структурного программирования и других идей,   лауреат премии Тьюринга 1972г. Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ, идея применения «семафоров » для синхронизации процессов в многозадачных системах, а так же разработка алгоритма нахождения кратчайшего пути на взвешенном графе без ребер отрицательного веса. Введение

3

Слайд 3: Задачи

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

4

Слайд 4: Последовательность шагов

Выбрать начальную вершину, присвоить стоимость пути до нее – 0, остальным вершинам ∞; Все вершины являются не выделенными; Объявить первую вершину текущей; Стоимости путей до всех невыделенных вершин находятся след. образом: стоимость пути до невыделенной вершины есть минимальное число из стоимости старого пути до данной вершины, равное сумме стоимости пути до текущей вершины и веса ребра соединяющего текущую и невыделенную вершины. Среди невыделенных вершин выбирается вершина с минимальной стоимостью пути до нее. Если такой вершины нет (стоимость путей до всех вершин равна ∞ ), то путь не существует и алгоритм завершается, иначе текущей вершиной становится найденная, и она же выделяется. Если все вершины являются выделенными (до всех них найден кратчайший путь), то алгоритм завершается, иначе переход на шаг 4. Последовательность шагов

5

Слайд 5: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Дан неориентированный граф без ребер отрицательного веса, необходимо найти в нем кратчайшие пути из вершины A до всех остальных вершин.

6

Слайд 6: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Шаги 1-3. Выберем вершину А в качестве первой, выделим ее и присвоим ей стоимость пути до нее равную 0, остальным же вершинам присвоим стоимость равную ∞.

7

Слайд 7: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Шаг 4. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной. 0+5=5 < ∞ ? Да

8

Слайд 8: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Шаг 4. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной. 0+5=5 < ∞ ? Да 0+2=2 < ∞ ? Да

9

Слайд 9: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Шаг 5. Среди невыделенных вершин выбирается вершина с минимальной стоимостью пути до нее. Если такой вершины нет (стоимость путей до всех вершин равна ∞), то путь не существует и алгоритм завершается, иначе текущей вершиной становится найденная, и она же выделяется

10

Слайд 10: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 2+2=4 < 5 ? Да Шаг 4. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной.

11

Слайд 11: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 2+2=4 < 5 ? Да Повторяем шаг 4 для новой вершины 2+10=12 < ∞ ? Да

12

Слайд 12: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 2+2=4 < 5 ? Да Повторяем шаг 4 для новой вершины 2+10=12 < ∞ ? Да 2+7=9 < ∞ ? Да

13

Слайд 13: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

14

Слайд 14: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 4+3=7 < 12 ? Да

15

Слайд 15: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 4+3=7 < 12 ? Да 4+2=6 < 9 ? Да

16

Слайд 16: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

17

Слайд 17: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 6+6=12 < ∞ ? Да

18

Слайд 18: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 6+6=12 < ∞ ? Да 6+4=10 < ∞ ? Да

19

Слайд 19: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

20

Слайд 20: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 7+5=12 < 10 ? Нет

21

Слайд 21: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 7+5=12 < 10 ? Нет 7+5=12 < 12 ? Нет

22

Слайд 22: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

23

Слайд 23: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 10+2=12 < ∞ ? Да

24

Слайд 24: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 5 для выделения новой вершины с минимальной стоимостью пути

25

Слайд 25: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Повторяем шаг 4 для новой вершины 12+3=15 < 12 ? Нет

26

Слайд 26: Нахождение кратчайшего пути в неориентированном графе

А B C D E G F H 5 2 2 2 10 3 7 5 5 4 6 2 3 Шаг 6. Все вершины выделены, до них найдены кратчайшие пути, алгоритм завершается.

27

Слайд 27: Результаты работы алгоритма

Были найдены следующие кратчайшие пути: A → A = 0 ; A → B = 4 ; A → C = 2 ; A → D = 7 ; A → E = 6 ; A → F = 12 ; A → G = 10 ; A → H = 12 ;

28

Последний слайд презентации: Структуры и алгоритмы обработки данных на ЭВМ Алгоритм Дейкстры

Спасибо за внимание!

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

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