Розробка програмної системи для обчислення найкоротших маршрутів з використанням алгоритму Дейкстри або Флойда та мови програмування С#

курсовая работа

1.2 Аналіз предметної області

Тема курсової роботи досить актуальна і по ній існує безліч різноманітних реалізацій.

Найпростіша реалізація алгоритму Дейкстри потребує O(V2) дій. У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 1 і перевіряємо всі сусідні з нею вершини. Якщо в ній відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то зменшуємо його. Цикл завершується коли позначки всіх вершин стають рівними 1.

Рисунок 1.1 - Реалізація алгоритму Дейкстри

На рисунку 1.1 зображено програму, що реалізує знаходження найкоротшого шляху зі алгоритмом Дейкстри (програма знаходиться у вільному доступі).

Делись добром ;)