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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3  Орграф

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

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

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

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

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

графах.

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

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

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

Dist(Xi)

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

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

D.

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

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

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

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

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

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

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

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

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

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

algor_Dijkst’.

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

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

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

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

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

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

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

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

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

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

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

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