Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Кратчайший путь

Содержание

Содержание:Графы: определения и примерыОриентированные графыПуть в орграфеМатрица смежностиИерархический списокАлгоритм ДейкстрыПрограмма “ProGraph”Описание работы программыДостоинства программыСписок литературы
Олимпиадная работа по ИКТ: “Нахождение кратчайшего пути с использованием графов и алгоритма Содержание:Графы: определения и примерыОриентированные графыПуть в орграфеМатрица смежностиИерархический списокАлгоритм ДейкстрыПрограмма “ProGraph”Описание работы программыДостоинства программыСписок литературы Графы: определения и примеры Говоря простым языком, граф - это множество точек Рис. 1. Три способа изображения одного графа Например, три графа на рис. 1 совпадают А два графа на рис. 2 - различны Рис. 2. Пример двух разных графов Степень вершиныЛюбому ребру соответствует ровно две вершины, а вот вершине может соответствовать Смежные вершины и рёбраДве вершины называются смежными, если они являются разными концами Путь в графеПуть в графе - это последовательность вершин (без повторений), в Достижимость Вершина v достижима из вершины u, если существует путь, начинающийся в Длина путиДлина пути - количество ребер, из которых этот путь состоит. Например, Примеры неориентированных графов Ориентированные графыОрграф - это граф, все ребра которого имеют направление. Такие направленные Смешанный графВ отличие от ребер, дуги соединяют две неравноправные вершины: одна из Путь в орграфеПуть в орграфе - это последовательность вершин (без повторений), в Примеры ориентированных графов Взвешенные графыВзвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), Длина пути во взвешенном графеДлина пути во взвешенном (связном) графе - это Примеры взвешенных графов Способы представления графов Существует довольно большое число разнообразных способов представления графов. Однако Матрица смежности Матрица смежности Sm - это квадратная матрица размером N x Пример матрицы смежностиРис. 4  Взвешенный граф Преимущества матрицы смежностиУдобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных Иерархический список  В одном линейном списке содержатся номера Пример иерархического спискаРис. 5  Пример иерархического списка Рис. 3  Орграф Преимущества иерархического списка  Вершина = запись   Номер:  Число; Программа “ProGraph”Программа “ProGraph” была специально созданна для создания графов в графической оболочке. Алгоритм ДейкстрыМы рассмотрим один из основных алгоритмов поиска кратчайших путей в графе Описание алгоритмаОсновная идея основана на простой формуле:   (Dist(x) – расстояние Описание алгоритма     Допустим, нам надо найти кратчайший путь Описание работы программыРабота делится на две части:Создание графа в Редакторе.Применение алгоритма Дейкстры Создание графа в РедактореЗапустите программу “ProGraph.exe” Вы увидите это окно.В данном окне Создание графа в РедактореУ вас должно получиться примерно так:Мы видим пример сети, Применение алгоритма ДейкстрыДля вызова программы загружаем (File -> Load) ранее сохранённый файл.Открываем Просмотр результатаВы увидите результат работы:В окне задания параметров появитсястрока с длиной кратчайшего Достоинства программыС помощью этой программы вы можете создать любой граф с помощьюудобного Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике:Международные олимпиады 1989 –
Слайды презентации

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

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

список
Алгоритм Дейкстры
Программа “ProGraph”
Описание работы программы
Достоинства программы
Список литературы



Слайд 3 Графы: определения и примеры
Говоря простым языком, граф -

Графы: определения и примеры Говоря простым языком, граф - это множество

это множество точек (для удобства изображения - на плоскости)

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

Слайд 4 Рис. 1. Три способа изображения одного графа
Например,

Рис. 1. Три способа изображения одного графа Например, три графа на рис. 1 совпадают

три графа на рис. 1 совпадают


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

А два графа на рис. 2 - различны Рис. 2. Пример двух разных графов


Рис. 2. Пример двух разных графов


Слайд 6 Степень вершины
Любому ребру соответствует ровно две вершины, а

Степень вершиныЛюбому ребру соответствует ровно две вершины, а вот вершине может

вот вершине может соответствовать произвольное количество ребер, это количество

и определяет степень вершины. Изолированная вершина вообще не имеет ребер (ее степень равна 0).

Слайд 7 Смежные вершины и рёбра
Две вершины называются смежными, если

Смежные вершины и рёбраДве вершины называются смежными, если они являются разными

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

смежными, если они выходят из одной вершины.

Слайд 8 Путь в графе
Путь в графе - это последовательность

Путь в графеПуть в графе - это последовательность вершин (без повторений),

вершин (без повторений), в которой любые две соседние вершины

смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и abc.



Слайд 9 Достижимость
Вершина v достижима из вершины u, если

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

существует путь, начинающийся в u и заканчивающийся в v.
Граф

называется связным, если все его вершины взаимно достижимы.

Слайд 10 Длина пути
Длина пути - количество ребер, из которых

Длина путиДлина пути - количество ребер, из которых этот путь состоит.

этот путь состоит. Например, длина уже упомянутых путей adbc

и abc - 3 и 2 соответственно.

Расстояние между между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. равно 2.

Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис.



Слайд 11 Примеры неориентированных графов

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

Слайд 12 Ориентированные графы

Орграф - это граф, все ребра которого

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

имеют направление. Такие направленные ребра называются дугами. На рисунках

дуги изображаются стрелочками ( рис.3)

Рис. 3.  Орграф


Слайд 13 Смешанный граф
В отличие от ребер, дуги соединяют две

Смешанный графВ отличие от ребер, дуги соединяют две неравноправные вершины: одна

неравноправные вершины: одна из них называется началом дуги (дуга

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

Слайд 14 Путь в орграфе
Путь в орграфе - это последовательность

Путь в орграфеПуть в орграфе - это последовательность вершин (без повторений),

вершин (без повторений), в которой любые две соседние вершины

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

Рис. 3.  Орграф


Слайд 15 Примеры ориентированных графов

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

Слайд 16 Взвешенные графы

Взвешенный (другое название: размеченный) граф (или орграф)

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

- это граф (орграф), некоторым элементам которого (вершинам, ребрам

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

Рис. 4  Взвешенный граф


Слайд 17 Длина пути во взвешенном графе
Длина пути во взвешенном

Длина пути во взвешенном графеДлина пути во взвешенном (связном) графе -

(связном) графе - это сумма длин (весов) тех ребер,

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

Рис. 4  Взвешенный граф


Слайд 18 Примеры взвешенных графов

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

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

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

представления графов. Однако мы изложим здесь только самые полезные

с точки зрения программирования.

Слайд 20 Матрица смежности
Матрица смежности Sm - это квадратная матрица

Матрица смежности Матрица смежности Sm - это квадратная матрица размером N

размером N x N (N - количество вершин в

графе), заполненная по следующему правилу:

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

Слайд 21 Пример матрицы смежности
Рис. 4  Взвешенный граф

Пример матрицы смежностиРис. 4  Взвешенный граф

Слайд 22 Преимущества матрицы смежности
Удобство матрицы смежности состоит в наглядности

Преимущества матрицы смежностиУдобство матрицы смежности состоит в наглядности и прозрачности алгоритмов,

и прозрачности алгоритмов, основанных на ее использовании. А неудобство

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

Слайд 23 Иерархический список
В одном линейном списке содержатся номера

Иерархический список В одном линейном списке содержатся номера

"начальных вершин", а в остальных - номера смежных вершин

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

Слайд 24 Пример иерархического списка
Рис. 5  Пример иерархического списка
Рис.

Пример иерархического спискаРис. 5  Пример иерархического списка Рис. 3  Орграф

3  Орграф


Слайд 25 Преимущества иерархического списка
Вершина = запись

Преимущества иерархического списка Вершина = запись  Номер: Число;  Имя:

Номер: Число;
Имя: Строка;

След Вершина: указатель на Вершина;
Список Дуг: Дуга;
end;

Дуга = запись
Стоимость: Число;
Конец Дуги: Вершина;
След Дуга: Дуга;
end;

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

Слайд 26 Программа “ProGraph”
Программа “ProGraph” была специально созданна для создания

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

графов в графической оболочке. Поддерживает возможность добавления алгоритмов на

графах.


Слайд 27 Алгоритм Дейкстры
Мы рассмотрим один из основных алгоритмов поиска

Алгоритм ДейкстрыМы рассмотрим один из основных алгоритмов поиска кратчайших путей в

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

графов с неотрицательными весами.



Слайд 28 Описание алгоритма
Основная идея основана на простой формуле:

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

(Dist(x) – расстояние до вершины x из исходной)

Dist(Xi)

= Минимум(Dist(Xi), Dist(p) +Matr(p,i))





Слайд 29 Описание алгоритма

Допустим, нам

Описание алгоритма   Допустим, нам надо найти кратчайший путь из

надо найти кратчайший путь из вершины A в вершину

D.

Перебираем все возможные расстояния до вершин, находим из них минимальное и выводим кратчайший путь.

Слайд 30 Описание работы программы
Работа делится на две части:

Создание графа

Описание работы программыРабота делится на две части:Создание графа в Редакторе.Применение алгоритма

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



Слайд 31 Создание графа в Редакторе
Запустите программу “ProGraph.exe”
Вы увидите

Создание графа в РедактореЗапустите программу “ProGraph.exe” Вы увидите это окно.В данном

это окно.
В данном окне вы должны
ввести параметры:
Количество вершин

графа
(‘AddNode’)
Ребра и их вес
(‘AddNode’, ‘Matrix’ – веса ребер)
Имена вершин
(ПКМ на вершине, поле ‘NodeName’)

Здесь вы можете дополнительно
выбрать графическое изображение
вершин.

Слайд 32 Создание графа в Редакторе
У вас должно получиться примерно

Создание графа в РедактореУ вас должно получиться примерно так:Мы видим пример

так:
Мы видим пример сети,
оформленной в виде графа.
Расстояние между

вершинами
показаны на линиях.
В оформлении вершин
используется пиктограмма
компьютера.

Для сохранения полученного
графа выбираем из меню
File -> Save as и сохраняем
под любым именем.

Полученную заготовку будем
использовать для второй части.


Слайд 33 Применение алгоритма Дейкстры
Для вызова программы загружаем (File ->

Применение алгоритма ДейкстрыДля вызова программы загружаем (File -> Load) ранее сохранённый

Load) ранее сохранённый файл.
Открываем из главного меню ‘ALGOR ->

algor_Dijkst’.

Появится новое окно, в котором необходимо задать начальный и конечный
номер вершины.


(Чтобы переключить показ
‘Имена вершин/Индексы’ необходимо
поставить флажок в поле ‘ShowNodInd’)

Заполнить поля ‘From’ и ‘To’
и запустить алгоритм на выполнение
(‘OK’)


Слайд 34 Просмотр результата
Вы увидите результат работы:

В окне задания параметров

Просмотр результатаВы увидите результат работы:В окне задания параметров появитсястрока с длиной

появится
строка с длиной кратчайшего пути и
сам путь.
В окне редактора

отобразится
пройденный путь и вершины окрасятся в
следующие цвета:

Красный – начальная вершина.
Синий – конечная вершина.
Желтый – вершины искомого пути.
Серый – вершины, посещенные при
работе алгоритма, но не включённые в
конечный путь.

Слайд 35 Достоинства программы
С помощью этой программы вы можете создать

Достоинства программыС помощью этой программы вы можете создать любой граф с

любой граф с помощью
удобного редактора графов: схема метро,
карта городов,

компьютерные сети, карту лабиринта и многое другое.

Представить его в графическом виде, добавляя названия вершин,
пиктограммы, расстояния.

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

Программа была создана на языке “Delphi” с использованием
объектно-ориентированного программирования.

Данная программа может быть использована для подготовки к ЕГЭ
по информатике.


  • Имя файла: kratchayshiy-put.pptx
  • Количество просмотров: 155
  • Количество скачиваний: 0