Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры”

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

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №2

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №3

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №4

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №5

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №6

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №7

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №8

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №9

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №10

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №11

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №12

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №13

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №14

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №15

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №16

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №17

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №18

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №19

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №20

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №21

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №22

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №23

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №24

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №25

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №26

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №27

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №28

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №29

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №30

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №31

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №32

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №33

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №34

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №35

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” , слайд №36

Содержание ▲

Вы можете ознакомиться и скачать Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры” . Презентация содержит 36 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

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

Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры”

Слайд 2

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

Содержание: Графы: определения и примеры Ориентированные графы Путь в орграфе Матрица смежности Иерархический список Алгоритм Дейкстры Программа “ProGraph” Описание работы программы Достоинства программы Список литературы

Слайд 3

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

Графы: определения и примеры Говоря простым языком, граф - это множество точек (для удобства изображения - на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит.

Слайд 4

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

Например, три графа на рис. 1 совпадают

Слайд 5

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

А два графа на рис. 2 - различны

Слайд 6

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

Степень вершины Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет ребер (ее степень равна 0).

Слайд 7

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

Смежные вершины и рёбра Две вершины называются смежными, если они являются разными концами одного ребра. Два ребра называются смежными, если они выходят из одной вершины.

Слайд 8

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

Путь в графе Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и abc.

Слайд 9

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

Достижимость Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Граф называется связным, если все его вершины взаимно достижимы.

Слайд 10

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

Длина пути Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Расстояние между между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. равно 2. Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис.

Слайд 11

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

Примеры неориентированных графов

Слайд 12

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

Ориентированные графы Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками ( рис.3)

Слайд 13

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

Смешанный граф В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Можно сказать, что любое ребро - это пара дуг, направленных навстречу друг другу. Если в графе присутствуют и ребра, и дуги, то его называют смешанным

Слайд 14

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

Путь в орграфе Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рис. 3 нет пути, ведущего из вершины 2 в вершину 5. "Двигаться" по орграфу можно только в направлениях, заданных стрелками.

Слайд 15

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

Примеры ориентированных графов

Слайд 16

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

Взвешенные графы Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Слайд 17

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

Длина пути во взвешенном графе Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 4, равно 6.

Слайд 18

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

Примеры взвешенных графов

Слайд 19

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

Способы представления графов Существует довольно большое число разнообразных способов представления графов. Однако мы изложим здесь только самые полезные с точки зрения программирования.

Слайд 20

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

Матрица смежности Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполненная по следующему правилу: Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = Ves(e), в противном случае Sm[u,v] = “-”.

Слайд 21

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

Пример матрицы смежности

Слайд 22

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

Преимущества матрицы смежности Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.

Слайд 23

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

Иерархический список В одном линейном списке содержатся номера "начальных вершин", а в остальных - номера смежных вершин или указатели на эти вершины. В качестве примера приведем иерархический список, задающий орграф, изображенный на рис.3

Слайд 24

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

Пример иерархического списка

Слайд 25

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

Преимущества иерархического списка Вершина = запись Номер: Число; Имя: Строка; След Вершина: указатель на Вершина; Список Дуг: Дуга; end; Дуга = запись Стоимость: Число; Конец Дуги: Вершина; След Дуга: Дуга; end; Очевидное преимущество такого способа представления графов заключается в экономичном использовании памяти. И даже небольшая избыточность данных, к которой приходится прибегать в случае неориентированного графа, задавая каждое ребро как две дуги, искупается гибкостью всей структуры, что особенно удобно при необходимости частых перестроений в процессе работы программы.

Слайд 26

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

Программа “ProGraph” Программа “ProGraph” была специально созданна для создания графов в графической оболочке. Поддерживает возможность добавления алгоритмов на графах.

Слайд 27

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

Алгоритм Дейкстры Мы рассмотрим один из основных алгоритмов поиска кратчайших путей в графе – алгоритм Дейкстры, применимый для графов с неотрицательными весами.

Слайд 28

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

Описание алгоритма Основная идея основана на простой формуле: (Dist(x) – расстояние до вершины x из исходной) Dist(Xi) = Минимум(Dist(Xi), Dist(p) +Matr(p,i))