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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изображение слайда
1/1
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, остальным же вершинам присвоим стоимость равную ∞.

Изображение слайда
Изображение для работы со слайдом
1/2
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 < ∞ ? Да

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
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 < ∞ ? Да

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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. Для каждой невыделенной вершины выполним вычисление: суммируем стоимость пути до текущей вершины и вес ребра соединяющего ее с невыделенной вершиной. Если эта сумма меньше стоимости пути до невыделенной вершины, то присваиваем найденную стоимость невыделенной вершине, иначе, продолжаем считать прежнюю стоимость пути до невыделенной вершины минимальной.

Изображение слайда
Изображение для работы со слайдом
1/2
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 < ∞ ? Да

Изображение слайда
Изображение для работы со слайдом
1/2
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 < ∞ ? Да

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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 ? Да

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
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 ? Да

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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 < ∞ ? Да

Изображение слайда
Изображение для работы со слайдом
1/2
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 < ∞ ? Да

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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 ? Нет

Изображение слайда
Изображение для работы со слайдом
1/2
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 ? Нет

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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 < ∞ ? Да

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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 ? Нет

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

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
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 ;

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

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

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

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