![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Лекция № 17
Тема: кратчайшие пути. Алгоритм Дейкстры Основные вопросы, рассматриваемые на лекции: 1. Задача о кратчайшем пути на графе. 2. Определение алгоритма Дейкстры. 3. Выполнение алгоритма Дейкстры на примере графа. Краткое содержание лекционного материала 1. Задача о кратчайшем пути на графе. Припишем всем ребрам графа веса – положительные числа. Кратчайший путь от вершины Пример. Маршрут Задача о кратчайшем пути на графе решается алгоритмом, изобретенным нидерландским ученым Э. Дейкстрой в 1959 г. Расстоянием от 2. Определение алгоритма Дейкстры. Каждой вершине Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшить метку вершины. Если все вершины посещены, алгоритм завершается. Метка вершины Для каждой не посещённой вершины Рассмотрев все не посещённые вершины, смежные с вершиной 4. Выполнение алгоритма Дейкстры на примере графа. Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных. Кружками обозначены вершины, линиями – ребра графа. В кружках обозначены номера вершин, над ребрами обозначена их вес – (или длина пути). Рядом с каждой вершиной обозначена метка – длина кратчайшего пути в эту вершину из вершины 1. Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. 7<¥, поэтому метка ¥ при вершине 2 заменяется меткой 7, 9<¥, поэтому метка ¥ при вершине 3 заменяется меткой 9, 14<¥, поэтому метка ¥ при вершине 6 заменяется меткой 14, вершина 1 вычеркивается из числа посещенных вершин. 7+10=17>9, поэтому метка 9 при вершине 3 остается; 7+15=22<¥, поэтому метка ¥ при вершине 4 заменяется меткой 22; вершина 2 вычеркивается из числа посещенных вершин. 9+11=20<22, поэтому метка 22 при вершине 4 заменяется меткой 20; 9+2=11<14, поэтому метка 14 при вершине 6 заменяется меткой 11; вершина 3 вычеркивается из числа посещенных вершин. 11+9=20<¥, поэтому метка ¥ при вершине 5 заменяется меткой 20; вершина 6 вычеркивается из числа посещенных вершин. 20+6=26>20, поэтому метка 20 при вершине 5 остается; вершина 4 вычеркивается из числа посещенных вершин. У вершины 5 не посещенных смежных вершин нет, поэтому вершина 5 также вычеркивается из числа не посещенных вершин. Алгоритм заканчивает работу, так как нельзя больше обработать ни одной вершины. Кратчайшие пути – это последние метки при вершинах.
Дата добавления: 2014-01-03; Просмотров: 323; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |