Визначення оптимального маршруту за допомогою алгоритму Дейкстри

Abstract

Пошуки найшвидших та найкоротших шляхів реалізуються різними способами. Проблема найкоротшого шляху, заснована на структурі даних, стала популярною темою дослідження в теорії графів. Це задача на знаходження шляху між двома вершинами (або вузлами) графа таким чином, щоб сума ваг складових його ребер була мінімізована. В якості основної теорії розв’язання цієї задачі в інженерних розрахунках широко використовується алгоритм Дейкстри. Його функцією є знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин. Слід зазначити, що класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

The search for the fastest and shortest ways is realized in different ways. The problem of the shortest path, based on data structure, has become a popular research topic in graph theory. This is the task of finding the path between two vertices (or nodes) of a graph so that the sum of the weights of the components of its edges is minimized. Dijkstra's algorithm is widely used in engineering calculations as the main theory for solving this problem. Its function is to find the shortest path from one vertex of the graph to all other vertices. It should be noted that the classic Dijkstra algorithm worksonly for graphs without negative length cycles.