PPt4Web Хостинг презентаций

Главная / Информатика / Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию

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

№ слайда 2 Графы: определения и примеры Графы: определения и примеры Ориентированные графы
Описание слайда:

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

№ слайда 3 Говоря простым языком, граф - это множество точек (для удобства изображения - на
Описание слайда:

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

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

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

№ слайда 6 Любому ребру соответствует ровно две вершины, а вот вершине может соответствоват
Описание слайда:

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

№ слайда 7 Две вершины называются смежными, если они являются разными концами одного ребра.
Описание слайда:

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

№ слайда 8 Путь в графе - это последовательность вершин (без повторений), в которой любые д
Описание слайда:

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

№ слайда 9 Вершина v достижима из вершины u, если существует путь, начинающийся в u и закан
Описание слайда:

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

№ слайда 10 Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже
Описание слайда:

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

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

№ слайда 12 Орграф - это граф, все ребра которого имеют направление. Такие направленные ребр
Описание слайда:

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

№ слайда 13 В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них назыв
Описание слайда:

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

№ слайда 14 Путь в орграфе - это последовательность вершин (без повторений), в которой любые
Описание слайда:

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

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

№ слайда 16 Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф),
Описание слайда:

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

№ слайда 17 Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из
Описание слайда:

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

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

№ слайда 19 Существует довольно большое число разнообразных способов представления графов. О
Описание слайда:

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

№ слайда 20 Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вер
Описание слайда:

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

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

№ слайда 22 Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, осно
Описание слайда:

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

№ слайда 23 В одном линейном списке содержатся номера "начальных вершин", а в оста
Описание слайда:

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

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

№ слайда 25 Вершина = запись Вершина = запись Номер: Число; Имя: Строка; След Вершина: указа
Описание слайда:

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

№ слайда 26 Программа “ProGraph” была специально созданна для создания графов в графической
Описание слайда:

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

№ слайда 27 Мы рассмотрим один из основных алгоритмов поиска кратчайших путей в графе – алго
Описание слайда:

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

№ слайда 28 Основная идея основана на простой формуле: (Dist(x) – расстояние до вершины x из
Описание слайда:

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

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

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

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

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

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

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

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

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

Скачать эту презентацию

Презентации по предмету
Презентации из категории
Лучшее на fresher.ru