In mathematical science and computer science there is a separate direction called graph theory. Within its framework, various problems are posed and solved, for example, on finding the shortest path between the peaks. One of the methods widespread among mathematicians for solving this problem has long been the Dijkstra algorithm.
What is a math graph
It is believed that the concept of the graph was introduced into everyday life in the eighteenth century by Leonard Euler. It was he who voiced the formulation and solution of one of the classical problems of this theory - the seven bridges of Koenigsberg. In order to explain the object of this theory, they often use an analogy such as movement between different cities. Then the graph on the plane will represent the entire route scheme, where the points will be specific points (for example, cities), and the edges will be the paths from one peak to another (an analogue of the road between cities). Dijkstra's algorithm, among other ways, can provide a solution to this issue.
Finding the Shortest Way
One of the standard problems of graph theory is one in which it is necessary to determine the optimal cost path between two points. It can be reduced on the plane to the solution of the graph, in which the peaks - cities - are interconnected by edges, which are possible roads. Moreover, each road has its own length, therefore, to travel along it will have to spend certain funds. This sum is equivalent to the weight of the edge on the graph. Then the task in practice can be formulated as follows: how to pave the way from one city to another in order to spend minimal money on the road.
Solutions
To solve this problem, some algorithms were invented that became widely known in the scientific world. For example, the Floyd-Warshell, Ford-Bellman algorithm. The classic way to find a solution is also Dijkstra's algorithm. It can be used both for a weighted (the weight of each edge is known) graph and for a sparse one. To find the final path, you need to do a few steps.
Dijkstra's Algorithm
The meaning of this method is that all vertices are traversed, starting with the given one, and each one is assigned a label with a certain value. Then, the vertices whose labels are minimal are included in the result. At the first step, the initial vertex is assigned a label with the value 0. Then all the following vertices are considered, that is, those that can be reached from the original. They are assigned labels, the value of which is defined as the sum of the source and the weight of the path. From the vertices of the next step, select the one that has the least label value, and examine all the vertices to which you can go from it without using intermediate vertices. A new label value is determined, equal to the vertex label - the source plus the weight of the path. If the received value is less than the vertex label, then the label changes. Otherwise, the original value remains. In this case, in a separate array, the dimension of which is equal to the number of vertices of the graph, the optimization result is saved, by which the path is determined. To implement a method such as Dijkstra's algorithm, Pascal offers very convenient tools. The algorithm has the advantage that it can easily be the basis of a program that is small in size. Examples of such software products are easy to find on the Internet.
To solve the problem of finding the optimal path, you can use various means. For a solution such as Dijkstra’s algorithm, Delphi will allow you to create a visual convenient form for inputting source data and outputting the final result.