Пошук оптимального маршруту (Алгоритм Дейкстри)
.1 Опис предметної області
Графічне подання рішення різних прикладних задач нам добре відомо. До графічних подань у широкому змісті можуть бути віднесені малюнки, креслення, графіки, діаграми, блок-схеми тощо. З їхньою допомогою наочно ілюструються залежності процесів і явищ, логічні, структурні, причинно-наслідкові і інші взаємозв’язки. Однак теорія графів має свою власну проблематику. У дискретній математиці граф є найважливішим математичним поняттям. На основі теорії графів будуються моделі різноманітних задач, таких як маршрутизації, розподілу ресурсів, дискретної оптимізації, сіткового планування і керування, аналізу і проектування організаційних структур, аналізу процесу їх функціонування і багато іншого.
Таким чином, граф – це спосіб візуалізації зв’язків між деякими об’єктами. Побудова математичного визначення графа здійснюється шляхом формалізації об’єктів та зв’язків як елементів деяких множин.
Графом
називається сукупність двох множин –
точок і
ліній, при цьому елементи множини
називаються вершинами, а елементи множини
– ребрами графа.