Алгоритм Дейкстри пошуку найкоротшого шляху графа. Програмна реалізація
Алгоритм віднаходження довжини найкоротшого шляху від фіксованої вершини до будь-якої іншої є алгоритм, який запропоновав у 1959р. датський математик Е. Дейкстра. Алгоритм Дейкстри може бути застосований для розв'язання багатьох прикладних задач.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 22.07.2024 |
| Размер файла | 22,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Алгоритм Дейкстри пошуку найкоротшого шляху графа. Програмна реалізація
Ольховецький Андрій, здобувач фахової передвищої освіти ІІІкурсу спеціальності "Комп'ютерна інженерія", науковий керівник канд. фіз.-мат. наук Стефурак Н.А.
Швидкі темпи розвитку IT-індустрії диктують свої вимоги до фахівців у цій сфері, одне з яких це вміння здійснювати алгоритмічні рішення (Problem Solving) прикладних задач [1]. Для прикладу, "алгоритмічні питання" можуть становити від 60% до 100% завдань співбесіди із кандидатами при працевлаштуванні в IT-компанію [2]. Як правило метою таких завдання є перевірка здатності фахівця до креативного, нестандартного мислення, а отже і здатності до розробки нового функціоналу програмного продукту та оптимізації існуючого. Тому знання і вміння застосовувати ефективні алгоритми є важливою компетенцією для розробників програмного забезпечення. Алгоритми використовуються практично в усіх сферах інформаційних технологій: в криптографії, при аналізі текстів, зображень і відео, в біоінформатиці, аналізі великих даних, штучному інтелекті, задачах оптимізації тощо.
Найефективніший алгоритм віднаходження довжини найкоротшого шляху від фіксованої вершини до будь-якої іншої є алгоритм, який запропоновав у 1959р. датський математик Е. Дейкстра.
Алгоритм Дейкстри може бути застосований для розв'язання багатьох прикладних задач, зокрема, знаходження найкоротшого шляху для GPS-навігації, оптимізації логістичних маршрутів доставки, знаходження найшвидшого шляху для передачі даних в мережах тощо.
Алгоритм працює із зваженими орієнтованими графами, які можуть мати лише додатну вагу кожного ребра. Нехай G = (V, Е) - орієнтований граф, w(vt, Vj)- вага дуги. Починаємо з вершин а і знаходимо віддаль від а до кожної із суміжних до неї вершин. Вибираємо вершину, віддаль від якої до вершини а є найменшою; нехай ця вершина буде V*. Далі знаходимо віддалі від вершини а до кожної вершини, суміжної з V* вздовж шляху, який проходить через вершину V*. Якщо для певної з таких вершин ця віддаль менша від поточної, то заміняємо нею поточну віддаль. Знову вибираємо вершину, найближчу до а, але таку, що не вибирали раніше, і процес повторюємо [3],[4]. алгоритм дейкстра математик
При реалізації даного алгоритму зручно користуватись методом міток, які будуть двох типів: тимчасові та постійні. Вершини з постійними мітками групують у множину М, яку називають множиною позначених вершин. Решта вершин має тимчасові мітки, і множину таких вершин позначають через Т (Т = V\M), де V - множина усіх вершин графа. Вихідній вершині присвоюється мітка 0 і мітки го для усіх інших вершин. Суть алгоритму зводиться до покрокового переприсвоювання значень міток. Величина постійної мітки дорівнює довжині найкоротшого шляху від вихідної вершини до заданої. Якщо ж мітка тимчасова, то вона дорівнює довжині найкоротшого шляху, який проходить лише через вершини з постійними мітками. Процес продовжується до того часу поки усі вершини не матимуть постійних міток [5].
У своїй роботі ми скористались алгоритмом Дейкстри для реалізації наступної прикладної задачі: необхідно знайти найкоротший шлях передачі інформаційного пакета між комп'ютерами локальної мережі. Структура мережі представлена змішаною топологією. Кількість комп'ютерів та відстані між ними відомі і є вхідними даними програмної системи. Після побудови математичної моделі конкретизованої задачі: у локальну мережу об'єднано 12 комп'ютерів за змішаною топологією, кожен вузол є вершиною зваженого орієнтованого графа, зв'язок між комп'ютерами на моделі представлено напрямленим ребром, а відстань - вагою ребра), яка зображена на рисунку 1:
даний алгоритм реалізовано на мовах C++ та Python. Основна ідея реалізації в обох мовах програмування полягає у використанні пріоритетної черги для зберігання вершин, які потрібно опрацювати, та використання структури даних, яка дозволяє зберігати граф. Проте є ряд відмінностей: у мові C++ використовуємо бібліотеку mathplolib, словник та масив для запису і обрахунку заданих значень, у мові Pathon використовуємо бібліотеки vector, queue, climits, вектор та масив.
Аналізуючи програмні коди обох мов програмування приходимо до висновку, що реалізація алгоритму найкоротшого шляху на мовах програмування C++ та Python дає можливість розробляти ефективні та функціональні рішення для вирішення прикладних задач, про те алгоритм працює ефективніше на мові C++ за рахунок швидкодії та економного використання пам'яті і є потужнішим при "вимогливих" застосуваннях, зокрема, при наукових обчисленнях, розробці ігор. Реалізація алгоритму на мові Python має перевагу у візуальному супроводі представлення результатів та має простий, зрозумілий для користувача синтаксис.
Програмна реалізація на обох мовах програмування може бути удосконалена та доопрацьована, зокрема, в частині оптимізації та модернізації програмного коду, розробці візуального програмного інтерфейсу, використання нових бібліотек і т.д.
Список використаних джерел
1. Прокоп Ю.В., Трофименко О.Г., Задерейко О.В. Аналіз підходів у викладанні початкового курсу програмування в університетах. Системні технології. 2021. "ІНФОРМАЦІЙНЕ СУСПІЛЬСТВО: ПРОБЛЕМИ ТА ПЕРСПЕКТИВИ" № 4(135). С. 73-84.
2. Прокоп Ю.В., Трофименко О.Г., Дикий О.В. Дослідження підходів до викладання курсу "Алгоритми та структури даних" для студентів ІТ-спеціальностей. Вчені записки Таврійського національного університету імені В.І. Вернадського. Серія "Технічні науки". 2021. Том 32 (71) Ч. 1 № 2. С. 216-220.
3. Нікольський Ю.В. Дискретна математика. К.: Видавнича група BHV, 2007. 387с.
4. М.Ф. Бондаренко Комп'ютерна дискретна математика: підручник. Харків. "Компания СМИТ". 2011. 485с.
5. Кривий С.Л. Дискретна математика: підручник для студентів вищ. навч. закл. Чернівці-Київ: Видавничий дім "Букрек". 2014. 568 с.
Размещено на Allbest.ru
...Подобные документы
Програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа. Загальні відомості про графи. Особливості роботи в середовищі. Опис структури програми та програмних засобів. Схема програмної реалізації алгоритму Дейкстри.
курсовая работа [676,7 K], добавлен 20.03.2011Особливість знаходження найкоротшого шляху між кожною парою вершин у графі. Формалізація алгоритму Флойда-Уоршелла. Багатократне застосування алгоритму Дейкстри з послідовним вибором кожної вершини графу. Аналіз допущення наявності дуг з від’ємною вагою.
отчет по практике [151,8 K], добавлен 04.12.2021Алгоритм сортування методом простого вибору. Знаходження найдовшого шляху в графі. Синтез машини Тюрінга, що розмічає послідовність чисел. Порівняння алгоритмів між собою за часом виконання і займаної пам'яті. Алгоритм пошуку мінімального елементу.
курсовая работа [90,3 K], добавлен 17.05.2011Задача на пошук найкоротшої відстані, маршруту і шляху холостого пробігу машин. Обгрунтування вибору методу та алгоритм розв'язання задачі. Опис математичної моделі задачі. Інтерфейс та лістинг программи. Заповнення таблиці суміжності для заданого графу.
курсовая работа [315,5 K], добавлен 26.05.2015Огляд суті гри "Доміно", характеристика її існуючих програмних реалізацій. Розробка евристичного алгоритму для розв’язання ігрової ситуації "Доміно". Програмна реалізація алгоритму мовою програмування високого рівня C#. Отладка оціночної функції.
курсовая работа [1,4 M], добавлен 14.05.2012Розробка програми для моделювання роботи алгоритму Дейкстри мовою C# з використанням об’єктно-орієнтованих принципів програмування. Алгоритм побудови робочого поля. Програмування графічного інтерфейсу користувача. Тестування програмного забезпечення.
курсовая работа [991,4 K], добавлен 06.08.2013Методика та порядок програмування алгоритмів циклічної структури із заданим числом повторень за допомогою мови програмування VAB. Алгоритм роботи з одновимірними масивами. Програмування алгоритмів із структурою вкладених циклів, обробка матриць.
курсовая работа [27,7 K], добавлен 03.04.2009Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.
контрольная работа [691,8 K], добавлен 08.09.2010Использование NP-трудных в сильном смысле задачи. Обслуживание требований без задержек. Алгоритм построения бесконтурного графа. Псевдополиномиальные сведения задач. Последовательный анализ вариантов допустимого расписания ориентированного графа.
курсовая работа [783,7 K], добавлен 15.06.2009Алгоритм створення відкритого і секретного ключів. Коректність схеми RSA. Шифрування і створення електронного підпису. Використання китайської теореми про залишки для прискорення розшифрування. Криптоаналіз та атаки на криптографічний алгоритм RSA.
контрольная работа [747,6 K], добавлен 19.11.2014Создание программного обеспечения для реализации алгоритма, позволяющего находить кратчайшее расстояние от одной из вершин графа до всех остальных, при условии, что ребра графа не имеют отрицательного веса. Примеры выполнения алгоритма Дейкстра.
курсовая работа [1,1 M], добавлен 11.01.2015Безопасное состояние информационной системы. Основные утверждения (факты). Алгоритм построения графа распределения ресурсов для стратегии избежания тупиков. Структуры данных для алгоритма банкира, пример его использования. Алгоритм обнаружения тупиков.
презентация [1,3 M], добавлен 24.01.2014Представление задач в виде графов AND/OR, примеры. Задача с ханойской башней. Формулировка процесса игры в виде графа. Основные процедуры поиска по заданному критерию. Эвристические оценки и алгоритм поиска. Пример отношений с определением задачи.
лекция [154,6 K], добавлен 17.10.2013Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
курсовая работа [1,1 M], добавлен 26.06.2012Відомості з теорії графів, методи отримання точних розв'язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп'ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
курсовая работа [335,6 K], добавлен 15.06.2015Визначення і розв’язання задачі Коші для звичайних диференціальних рівнянь першого порядку методом Ейлера, алгоритм розв’язання, похибка при вирішенні. Складання блок-схеми. Реалізація алгоритму у середовищі Borland Pascal. Результат роботи програми.
курсовая работа [264,0 K], добавлен 20.08.2010Определение понятия "алгоритм". Изображение схемы алгоритма. Разработка схемы действий и этапы решения задач. Рассмотрение функции разрабатываемого приложения. Распределение исходного кода по файлам проекта. Контрольный пример и описание результатов.
реферат [695,9 K], добавлен 28.09.2014Структурна схема моделі (пакет MATLAB) та її описання. Математична модель у вигляді передавальних функцій, у вигляді диференційного рівняння. Алгоритм рішення (рекурентне співвідношення) та його програмна реалізація. Системи диференційних рівнянь.
курсовая работа [551,8 K], добавлен 14.02.2009Розробка постановки та алгоритму автоматизованого вирішення задачі, при розв'язанні якої на друк видається машинограма, яка містить дані про суму виплаченої заробітної плати та сплачених податків. Склад і опис вхідних повідомлень, алгоритм задачі.
лабораторная работа [1,4 M], добавлен 23.05.2015Розробка програми для розв’язання квадратних рівнянь з текстовим та графічним інтерфейсами користувача без дублювання їх коду. Алгоритм розв’язання квадратного рівняння у програмах з будь-яким інтерфейсом користувача, а саме: "консольний" та "форма".
лабораторная работа [14,9 K], добавлен 14.05.2011
