Поиск кратчайшего маршрута элементами динамического программирования и методом дейкстры

Abstract

В современном мире существует огромное количество дорог в виде сетей, причем сетей достаточно разветвленных, избыточных, а, следовательно, неоптимальных. При решении некоторых логистических вопросов, так или иначе, возникает прикладная и очень актуальная задача поиска кратчайшего расстояния между двумя пунктами сети. В данной работе для решения такой задачи предлагаются два метода. Первый метод непосредственно связан с динамическим программированием, а второй метод – метод Дейкстры – относится к аппарату дискретной математики -теории графов.

In the modern world, there are a huge number of roads in the form of networks, and networks are quite extensive, redundant, and, consequently, suboptimal. When solving some logistical issues, one way or another, there is an applied and very urgent task of finding the shortest distance between two points of the network. In this paper, two methods are proposed to solve this problem. The first method is directly related to dynamic programming, and the second method – Dijkstra's method – refers to the apparatus of discrete mathematics -graph theory.