January 7, 2011 at 00:34Dijkstra's algorithm. Search for optimal routes on the graph
Of the many algorithms for finding the shortest routes on a graph, on Habr I found only a description of the Floyd-Warshall algorithm. This algorithm finds the shortest paths between all vertices of the graph and their length. In this article I will describe the principle of operation of the Dijkstra algorithm, which finds the optimal routes and their length between one specific vertex (source) and all other vertices of the graph. The disadvantage of this algorithm is that it will not work correctly if the graph has arcs of negative weight.
As an example, we take the oriented graph G:
We can represent this graph in the form of a matrix C:
Take vertex 1 as a source. This means that we will look for the shortest routes from vertex 1 to vertices 2, 3, 4, and 5.
This algorithm step by step iterates over all the vertices of the graph and assigns labels to them, which are the known minimum distance from the source vertex to a specific vertex. Consider this algorithm as an example.
Assign the 1st vertex a label equal to 0, because this vertex is the source. The remaining vertices will be assigned labels equal to infinity.
Next, we choose a vertex W that has a minimal label (now this is vertex 1) and consider all the vertices to which from the vertex W there is a path that does not contain intermediary vertices. We assign a label to each of the vertices considered equal to the sum of the label W and the length of the path from W to the vertex in question, but only if the sum obtained is less than the previous label value. If the amount is not less, then leave the previous label unchanged.
After we have examined all the vertices to which there is a direct path from W, we mark the vertex W as visited, and choose from those not yet visited one that has the minimum label value, it will be the next vertex W. In this case, this is vertex 2 or 5. If there are several vertices with the same labels, it does not matter which one we choose as W.
We will select vertex 2. But there is not a single outgoing path from it, so we immediately mark this vertex as visited and move on to the next vertex with a minimum mark. This time only vertex 5 has a minimal label. Consider all the peaks to which there are straight lines of 5, but which are not yet marked as visited. Again we find the sum of the label of the vertex W and the weight of the edge from W to the current vertex, and if this sum is less than the previous label, then we replace the label value with the received sum.
Based on the picture, we can see that the labels of the 3rd and 4th peaks became smaller, that is, a shorter route to these peaks was found from the top of the source. Next, mark the 5th vertex as visited and select the next vertex that has a minimum label. We repeat all the above actions until there are unvisited peaks.
Having completed all the actions we get the following result:
There is also a vector P, from which it is possible to construct the shortest routes. By the number of elements, this vector is equal to the number of vertices in the graph. Each element contains the last intermediate vertex on the shortest path between the source vertex and the final vertex. At the beginning of the algorithm, all elements of the vector P are equal to the vertex of the source (in our case, P = {1, 1, 1, 1, 1}). Next, at the stage of recalculating the label value for the vertex under consideration, if the label of the vertex under consideration changes to a smaller one, we write the value of the current vertex W. to the array P. For example: the 3rd vertex had a label with the value “30”, for W = 1. Further, at W = 5, the label of the 3rd vertex changed to “20”, therefore we will write the value into the vector P - P [3] = 5. Also, at W = 5, the value of the label at the 4th vertex changed (it was “50”, it became “40”), then you need to set the 4th element of vector P to W - P [4] = 5. As a result, we obtain the vector P = {1, 1, 5, 5, 1}.
Knowing that in each element of the vector P the last intermediate vertex is recorded on the path between the source and the final vertex, we can get the shortest route itself.
As an example, we take the oriented graph G:
We can represent this graph in the form of a matrix C:
Take vertex 1 as a source. This means that we will look for the shortest routes from vertex 1 to vertices 2, 3, 4, and 5.
This algorithm step by step iterates over all the vertices of the graph and assigns labels to them, which are the known minimum distance from the source vertex to a specific vertex. Consider this algorithm as an example.
Assign the 1st vertex a label equal to 0, because this vertex is the source. The remaining vertices will be assigned labels equal to infinity.
Next, we choose a vertex W that has a minimal label (now this is vertex 1) and consider all the vertices to which from the vertex W there is a path that does not contain intermediary vertices. We assign a label to each of the vertices considered equal to the sum of the label W and the length of the path from W to the vertex in question, but only if the sum obtained is less than the previous label value. If the amount is not less, then leave the previous label unchanged.
After we have examined all the vertices to which there is a direct path from W, we mark the vertex W as visited, and choose from those not yet visited one that has the minimum label value, it will be the next vertex W. In this case, this is vertex 2 or 5. If there are several vertices with the same labels, it does not matter which one we choose as W.
We will select vertex 2. But there is not a single outgoing path from it, so we immediately mark this vertex as visited and move on to the next vertex with a minimum mark. This time only vertex 5 has a minimal label. Consider all the peaks to which there are straight lines of 5, but which are not yet marked as visited. Again we find the sum of the label of the vertex W and the weight of the edge from W to the current vertex, and if this sum is less than the previous label, then we replace the label value with the received sum.
Based on the picture, we can see that the labels of the 3rd and 4th peaks became smaller, that is, a shorter route to these peaks was found from the top of the source. Next, mark the 5th vertex as visited and select the next vertex that has a minimum label. We repeat all the above actions until there are unvisited peaks.
Having completed all the actions we get the following result:
There is also a vector P, from which it is possible to construct the shortest routes. By the number of elements, this vector is equal to the number of vertices in the graph. Each element contains the last intermediate vertex on the shortest path between the source vertex and the final vertex. At the beginning of the algorithm, all elements of the vector P are equal to the vertex of the source (in our case, P = {1, 1, 1, 1, 1}). Next, at the stage of recalculating the label value for the vertex under consideration, if the label of the vertex under consideration changes to a smaller one, we write the value of the current vertex W. to the array P. For example: the 3rd vertex had a label with the value “30”, for W = 1. Further, at W = 5, the label of the 3rd vertex changed to “20”, therefore we will write the value into the vector P - P [3] = 5. Also, at W = 5, the value of the label at the 4th vertex changed (it was “50”, it became “40”), then you need to set the 4th element of vector P to W - P [4] = 5. As a result, we obtain the vector P = {1, 1, 5, 5, 1}.
Knowing that in each element of the vector P the last intermediate vertex is recorded on the path between the source and the final vertex, we can get the shortest route itself.