One of the common tasks of graph theory is the one in which you need to find the most optimal path between two points. It can be solved on the plane as the graph in which the vertices - cities - are interconnected with ribs, which could be possible roads. And each road has its own length; therefore, traveling through it will take some resources. This amount is equivalent to the weight of the edge of the graph. Then the problem in practice can be formulated as follows: how to pave the way from one city to another, to spend the minimum resources on the road. The solution of this problem can be obtained by the Dijkstra algorithm.
Let’s consider initial vertex as a 0. This means that we will look for the shortest route from the vertex 0 to the other ones.
This algorithm goes step by step through all the vertices and assigns them labels, which are the minimum distances from an initial vertex to a particular node.
Let’s assign 0 to the 1st mark, because this vertex is initial.
Next, we choose a vertex that has a minimum label and look at all the vertices, to which there is a path from it. Each of the peaks gets the label, the amount equal to the initial label plus a length of a path from it to the considered vertex, but only if the amount is less than the previous value of the label. If the amount is not less, then we leave unchanged the previous label.
After we looked at all the vertices, in which there is a direct path from the start, we note the initial vertex as visited and choose one which has a minimum value of the label from not visited, and it will be the next initial vertex. If there are multiple nodes with the same label, it does not matter which one we choose as the primary.
Again we find the sum of the initial vertex label and weight the edge, and if that amount is less than the previous label, then we replace the label with a received amount.
Then we note this vertex as visited and choose the next vertex, which has the minimum label. We repeat all the steps above until there are unvisited vertices.
After completing all the steps, we get the following result:
Program execution
For a software implementation of the algorithm, we will need two arrays, logical “visited” - to store information about visited vertices and numerical “distance”, in which the shortest path would be placed. Thus, there exists a graph G = (V, E).
Each of the peaks included in the set of the V, was originally marked as unvisited, it means that elements of the “visited” array are set to “false”. As we must find the most profitable paths, in each element of the “distance” vector the number that is certainly larger than any potential path is recorded.
As a starting point is selected vertex s, and it is attributed to the zero path:. Distance [s] = 0, as there is no edge from s to s.
Then, all neighboring vertices (in which there is an s edge) [let those be t and u] are found, and investigated, the cost of the route from s to each of them is calculated:
distance [t] = distance [s] + s and t incident weight ribs;
distance [u] = distance [s] + s, and u incident weight ribs.
There you can see Dijkstra's algorithm written in C++ (http://www.hastuts.com/dijkstra-shortest-path-algorithm-in-cpp/)
But it is likely that there are several ways to the s vertex, so the cost in the distance array will have to be revised, then the highest value is ignored, and the smallest is associated with the vertex.
After processing the vertices adjacent to s it is marked as the visited: visited [s] = true and vertex the path from s to which is minimum becomes active.
Assume the path from u to s shorter than s to t, hence, vertex u becomes active in the way described above and its neighbors except the vertex s are investigated. Furthermore, u is marked as visited: visited [u] = true, vertex t becomes active, and the whole procedure is repeated for it. Dijkstra's algorithm can be extended as long as some of the s vertexes won’t be investigated.
Algorithm of a Dutch scientist Edsger Dijkstra finds the shortest path from one vertex to all the others. With its help, in the presence of all the necessary information, it is possible, for example, to learn how better to use a sequence of roads to get from one city to many others, and to which countries it is more profitable to export oil. The downside of this method is the impossibility of processing graphs, in which there are ribs with negative weight.
References: 1
Follow me, to be the first to learn about my publications devoted to popular science and educational topics
With Love,
Kate