Поиск оптимального маршрута (Алгоритм Дейкстры)

Пошук оптимального маршруту (Алгоритм Дейкстри)

.1 Опис предметної області

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

Таким чином, граф – це спосіб візуалізації зв’язків між деякими об’єктами. Побудова математичного визначення графа здійснюється шляхом формалізації об’єктів та зв’язків як елементів деяких множин.

Графом

називається сукупність двох множин –

точок і

ліній, при цьому елементи множини

називаються вершинами, а елементи множини

– ребрами графа.