The dextra algorithm and its implementation
In mathematical science and computer science there isA separate direction, called graph theory. Within its framework, various tasks are set and solved, for example, about finding the shortest path between the vertices. One of the most common methods for solving this problem among mathematicians has long been the Dijkstra algorithm.
It is believed that the notion of a graph was introduced inthe use 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 - about the seven bridges of Koenigsberg. In order to explain the object of this theory, most often use such an analogy as the movement between different cities. Then the graph on the plane will represent the whole scheme of routes, where the vertices will be specific points (for example, cities), and the edges - the path from one peak to another (analogous to the road between cities). Dijkstra's algorithm, in addition to other methods, can give a solution to this question.
One of the standard problems of graph theory isthe one in which it is necessary to determine the cost-optimal path between two points. It can be reduced on a plane to the solution of a graph in which the vertices-cities-are interconnected by edges, which represent possible roads. And each road has its own length, therefore, to travel through it will have to spend certain funds. This sum is equivalent to the weight of an edge on the graph. Then the problem in practice can be formulated as follows: how to pave the way from one city to another, to spend on the road a minimum of funds.
Solutions
To solve this problem, somealgorithms that have become widely known in the scientific world. For example, the algorithm Floyd - Warshell, Ford - Bellman. The Dijkstra algorithm is also a classic way of finding the solution. It can also be used for weighted (the weight of each edge is known) graph, and for sparse. To find the final path, you need to do a few steps.
Dijkstra Algorithm
The meaning of this method is thatall vertices are bypassed, beginning with a given one, each being given a label with a certain value. Then the result will include those vertices whose labels are minimal. In the first step, the original vertex is assigned a label with a value of 0. Then all the following vertices are considered, that is, those that can be accessed from the source vertex. They are assigned labels whose value is defined as the sum of the source and the weight of the path. From the vertices of the next step, one is chosen that has the smallest value of the label, and all the vertices to which it can be traversed without using intermediate vertices are studied. A new value of the label is defined, equal to the label of the source vertex plus the weight of the path. If the resulting value is less than the vertex label, then the label changes. Otherwise, the original value remains. In this case, in a separate array, whose dimension is equal to the number of vertices of the graph, the result of optimization is preserved, along which the path is determined. To implement such a method as the Dijkstra algorithm, Pascal offers very convenient tools. The algorithm has the advantage that it can easily be used as the basis of a program that has a small size. Examples of such software products are easy to find on the Internet.
