Практическая работа №8 по дисциплине: Теория алгоритмов наименование работы: Алгоритм Дейкстры.


Смоленский колледж телекоммуникаций
(филиал) федерального государственного образовательного
бюджетного учреждения высшего профессионального образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
Практическая работа №8
по дисциплине: Теория алгоритмов
наименование работы: Алгоритм Дейкстры.
для специальностей: 230115, 09.02.03
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.
Смоленск, 2014
1. Цель работы: овладеть навыками нахождения кратчайших путей в графе при помощи алгоритма Дейкстры.
2. Литература:
2.1. Балюкевич, Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2009.— 188 c. ISBN:978-5-374-00220-1
2.2. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c. ISBN:978-5-4439-0014-8
2.3. Гаврилов, Г.П. Задачи и упражнения по дискретной математике [Электронный ресурс]: учебное пособие/ Гаврилов Г.П., Сапоженко А.А.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 416 c. ISBN:978-5-9221-0477-7
3. Подготовка к работе:
3.1. Повторить тему «Алгоритмы на графах».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулировать определение графа?
3.3.2. Какие вершины называются инцидентными?
3.3.3. Какой граф называется взвешенным?
4. Основное оборудование: ПЭВМ
5. Задание:
Выполните задание согласно варианту.
5.1. Составить алгоритм и разработать программу нахождения кратчайших путей в графе при помощи алгоритма Дейкстры . Граф задан матрицей смежности.
Вариант 1 Вариант 2 Вариант 3
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 2 1 1 2 1 1 1 3 1 1 1 1 1 3 1 1 3 1 1
4 1 1 1 4 1 4 1 5 1 1 5 1 5 1
6 1 1 1 1 1 6 6
Вариант 4 Вариант 5 Вариант 6
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 1 1 3 1 1 3 1 1 1 3 1 1 1 1
4 1 4 1 1 4 1 1 1
5 1 5 1 5 1 1 1 1 1
6 6 6 1 1 1 Вариант 7 Вариант 8 Вариант 9
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 1 1 1
3 1 1 1 3 1 1 1 3 1 1 4 1 4 1 1 4 1 1 1
5 1 5 1 5 1 1 1
6 6 6 1 1 1 Вариант 10 Вариант 11 Вариант 12
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 1 1 2 1 1 3 1 1 3 1 1 3 1 1 1 1 1
4 1 4 1 1 4 1 1 1 1
5 1 5 5 1 1 1
6 6 6 1 1 1 1 Вариант 13 Вариант 14 Вариант 15
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 2 1 1 1 2 1 1 1 1 3 1 1 3 1 1 1 3 1 1 1 1
4 1 4 1 1 4 1 1 1 1 5 1 5 1 5 1 1 1 1 6 6 6 1 1 6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задание 5 письменно.
6.4. Сообщить преподавателю о выполненных заданиях.
6.5. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:
Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск Завершение работы Выключить компьютер (Alt+F4→ Завершение работы).
Выключите системный блок.
6.6. Приступить к выполнению тестирование программ.
6.7.Оформить отчет.
7. Содержание отчета:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить выполненные задания согласно варианта, текст программы с комментариями.
7.4. Ответы на контрольные вопросы.
8. Контрольные вопросы:
8.1. Сформулировать определение матрицы смежности?
8.2. Какие способы описания графа вы знаете?
8.3. Сформулировать определение матрицы инцидентности?
8.4. Объясните суть алгоритма Дейкстры?
8.5. Как граф представляется в памяти компьютера?
Составил преподаватель __________________________Скряго О.С.
9. Приложение:
Граф — совокупность точек, соединённых между собой линиями. Точки называют вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр. Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или рёбрами (если направленность двусторонняя, то есть направления равноправны).
Две вершины, соединенные ребром (дугой) называются смежными.
Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.
Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины с какими рёбрами (дугами) соединены и, возможно, указаны веса вершин и рёбер (дуг). Определение всех этих элементов и составляет суть формализации в этом случае.
Представление графа в памяти компьютера
Определим граф G как пару (V,E), где V – конечное множество вершин, а Е – множество неупорядоченных и упорядоченных пар вершин. Мощности множеств V и E обозначим буквами N и M. (Мощность конечного множества совпадает с количеством элементов в нем.) Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Единственное структурное различие между ориентированным и неориентированным графом состоит в том, что в первом случае граничные вершины ребра образуют упорядоченную пару, а во втором неупорядоченную. Говорят, что ребро (U, V) соединяет вершины U и V. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его 2-х вершин называютя инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам и дугам. Направление дуги графа на рисунке обозначается стрелкой. В 3-х мерном пространстве любой граф можно представить таким образом, что линии не будут пересекаться.
В прикладных задачах теории графов необходимость введения ориентации ребер возникает по 2-м причинам. Например, в системах городских улиц необходимо изображать улицы с одностороннем движением. При описании систем связи между людьми или машинами необходимо учитывать существенно однонаправленные устройства. С другой стороны, введение ориентации необходимо для установления системы координат и устранения неоднозначности.
Например, при соединении электрических приборов одно направление необходимо обозначить как положительное, для того чтобы однозначно описать распределение электрического тока, хотя действительное направление может и не быть жестко ограничено.
Способы описания графа:
Выбор подходящей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются способы описания графа: матрица инцидентности графа; матрица смежности графа; списки связи и перечня ребер.
Для хранения перечня ребер необходим 2- мерный массив Х размерности 2*М. Каждая строка массива описывает одно ребро.
Пример:
l1
l2
l3
l4
V1
V2
V3

l1 V1 V3
l2 V1 V2
l3 V1 V2
l4 V2 V3
Матрица смежности – это двумерный массив А размерности N*N
1, если вершины i и j - смежные
A[i,j]=
0, если вершины i и j - несмежны

V3
V1
V2
V4
V5
V8
V7
V6
Пример: Данный граф можно представить в виде матрицы смежности:
V1 V2 V3 V4 V5 V6 V7 V8
V1 0 0 0 0 0 0 0 0
V2 1 0 0 0 0 0 0 0
V3 0 1 0 1 1 0 0 0
A= V4 0 0 0 0 1 0 0 0
V5 0 1 0 0 0 0 0 0
V6 0 0 0 0 0 0 1 1
V7 0 0 0 0 0 0 0 1
V8 0 0 0 0 0 0 0 0
Матрица инцидентности графа, имеющего n вершин и m ребер– это двумерный массив А размерности N*M
e2
e1
e3
e5
e4
e6
V3
V1
V2
V4
V5
1, если j-е ребро инцидентно i-й вершине
A[i,j]=
0, если j-е ребро неинцидентно i-й вершине.

e1 e2 e3 e4 e5 e6
v1 1 0 0 0 0 0
v2 1 1 0 0 0 1
v3 0 1 1 0 1 0
v4 0 0 1 1 0 0
v5 0 0 0 1 1 1
Любая задача,требующая нахождения оптимальных маршрутов может быть выполнена с помощью алгоритма Дейкстры. Это касается и сетей, и транспортных потоков, и обработка графов. Очень часто используется не сам алгоритм в чистом виде, а его модификация.
Примеры:
1. При эвакуации населения из очагов бедствия оптимальные маршруты до пунктов сбора транспорта для каждой группы людей(дом,улица,школа и т.д) в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.
2. Компьютерная игра. Указываете точку назначения для персонажа и он движется туда по кратчайшему маршруту. Это тоже алгоритм Дейкстры.
3. Дана сеть автомобильных дорог, соединяющих города Гомельской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Гомеля до каждого города области (если двигаться можно только по дорогам).
4. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Милана до Минска.
Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
OSPF разбивает процесс построения таблицы маршрутизации на 2 этапа.
Второй этап состоит в нахождении оптимальных маршрутов с помощью полученного графа. Задача нахождения оптимального пути на графе является достаточно сложной и ёмкой. В протоколе OSPF для её решения используется итеративный алгоритм Дейкстры. Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг - до следующего маршрутизатора, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов".
Алгоритм
1. Каждой вершине в ходе алгоритма присваивается число , равное длине кратчайшего пути из вершины в вершину и включающем только окрашенные вершины. Положить и для всех остальных вершин графа. Окрашиваем вершину и полагаем , где – последняя окрашенная вершина.
2. Для каждой неокрашенной вершины пересчитывается величина по следующей формуле:

3. Если для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением и полагаем .
4. Если , кратчайший путь из в найден. Иначе переходим к шагу 2.
Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине . Это дерево называют ориентированным деревом кратчайших путей. Путь из в принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.
Отметим, что главным условием успешного применения алгоритма Дейкстры к задаче на графе является неотрицательность длин дуг этого графа
Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами.
Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:

№ Алгоритм Конкретные действия
1. Инициализация. Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1.
Задаем стартовые условия: d(1)=0, d(x)=∞.
Окрашиваем вершину № 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу: .
Составим матрицу длин кратчайших дуг для данного графа.
№/№ 1 2 3 4 5 6
1 7 9 14
2 7 10 15
3 9 10 11 2
4 15 11 6
5 6 9
6 14 2 9
или

2. Первый шаг.
Рассмотрим шаг алгоритма Дейкстры. d(2)=min{d(2) ; d(1)+a(1,2)}=min{∞; 0+7}=7
d(3)=min{d(3) ; d(1)+a(1,3)}=min{∞; 0+9}=9
d(4)=min{d(4) ; d(1)+a(1,4)}=min{∞; 0+∞}=∞
d(5)=min{d(5) ; d(1)+a(1,5)}=min{∞; 0+∞}=∞
d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+14}=14
Минимальную длину имеет путь от вершины № 1 до вершины № 2 d(2)=7.
Включаем вершину № 2 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,2).
3. Второй шаг. d(3)=min{d(3) ; d(2)+a(2,3)}=min{9; 7+10}=9
d(4)=min{d(4) ; d(2)+a(2,4)}=min{∞; 7+15}=22
d(5)=min{d(5) ; d(2)+a(2,5)}=min{∞; 7+∞}=∞
d(6)=min{d(6) ; d(2)+a(2,6)}=min{14; 7+∞}=14
Минимальную длину имеет путь от вершины № 1 до вершины № 3 d(3)=9.
Включаем вершину № 3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,3)
4. Третий шаг. d(4)=min{d(4) ; d(3)+a(3,4)}=min{22; 9+11}=20
d(5)=min{d(5) ; d(3)+a(3,5)}=min{∞; 9+∞}=∞
d(6)=min{d(6) ; d(3)+a(3,6)}=min{14; 9+2}=11
Минимальную длину имеет путь от вершины № 1 до вершины № 6 d(6)=11.
Включаем вершину № 6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,6)=(1,3)+(3,6)
5. Четвертый шаг. d(4)=min{d(4) ; d(6)+a(6,4)}=min{20; 11+∞}=20
d(5)=min{d(5) ; d(6)+a(6,5)}=min{∞; 11+9}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 4 и № 5 d(4)=d(6)=20.
Включаем вершину № 4 и № 5 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,4)=(1,3)+(3,4) и (1,5)=(1,3)+(3,6)+(6,5).
6. Заключение. Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0
d(2)=1-2 Длина маршрута L=7
d(3)=1-3 Длина маршрута L=9
d(4)=1-3-4 Длина маршрута L=20
d(5)=1-3-6-5 Длина маршрута L=20
d(6)=1-3-6 Длина маршрута L=11

Приложенные файлы

  • docx 23
    Скряго
    Размер файла: 92 kB Загрузок: 0

Добавить комментарий