Solve the problem of finding the shortest path using Dijkstra's algorithm.
Find the shortest path from X0 to X7. The graph is defined by the elements of the cost matrix
Let's build this graph 
Let's start with the element X0 and assign it the label 0, consider all its neighbors, because There are no marks there yet, so let’s assign them the appropriate lengths: 
All neighbors of X0 have been considered, mark it and move on to vertex X1. Its neighbors are X0, X2, X4, but X0 is marked, so we don’t consider it. For X2: 
, leave a mark.
For X4: 
, replace the label. All neighbors of vertex X1 have been considered, mark it 
go to top X2. ITS neighbors X0, X1, X3, X4, X5, X6, but X0, X1 are marked, we do not consider them.
For X3: 
, leave a mark.
For X5: 
, replace the label.
For X4: 
, leave a mark.
For X6: 
, replace the label.
All neighbors of vertex X2 have been considered, so we mark it. 
we move to the top of X3. ITS neighbors X0, X2, X6, but X0, X2 are marked, we do not consider them.
For X6: 
, leave a mark.
All neighbors of vertex X3 have been considered, so we mark it. 
we move to the top of X4. ITS neighbors X1, X2, X5, X7, but X1, X2 are marked, we do not consider them.
For X5: 
, replace the label.
For X7: 
, replace the label.
All neighbors of vertex X4 have been considered, so we mark it. 
we move to the top of X5. ITS neighbors X2, X4, X6, X7, but X2, X4 are marked, we do not consider them.
For X6: 
, leave a mark.
For X7: 
, leave a mark.
All neighbors of vertex X5 have been considered, we mark it. 
go to top X6. ITS neighbors X2, X3, X5, X7, but X2, X3, X5 are marked, we do not consider them.
For X7: 
, leave a mark.
All neighbors of vertex X6 have been considered, so we mark it. And we mark the remaining X7, all vertices have been considered. 
Conclusion: The shortest path of their X0 to X7 has a length of 101, this path: X7-X4-X1-X0.
Let's look at the example of finding the shortest path. A network of highways connecting the regions of the city is given. Some roads are one way. Find the shortest routes from the city center to each city in the region.
To solve this problem you can use Dijkstra's algorithm is a graph algorithm invented by the Dutch scientist E. Dijkstra in 1959. Finds the shortest distance from one of the vertices of the graph to all the others. Only works for graphs without negative weight edges.
Suppose you need to find the shortest distances from the 1st vertex to all the others.
The circles indicate the vertices, the lines indicate the paths between them (the edges of the graph). The numbers of the vertices are indicated in the circles, their weight is indicated above the edges - the length of the path. Next to each vertex there is a red mark - the length of the shortest path to this vertex from vertex 1.
The label of vertex 1 itself is set to 0, the labels of other vertices are set to unreachable big number(ideally infinity). This reflects that the distances from vertex 1 to other vertices are not yet known. All vertices of the graph are marked as unvisited. 
First step
Vertex 1 has the minimum label. Its neighbors are vertices 2, 3 and 6. We go around the neighbors of the vertex in turn.
The first neighbor of vertex 1 is vertex 2, because the length of the path to it is minimal. The length of the path to it through vertex 1 is equal to the sum of the shortest distance to vertex 1, the value of its label, and the length of the edge going from 1st to 2nd, that is, 0 + 7 = 7. This is less than the current label of vertex 2 (10000) , so the new label of the 2nd vertex is 7. 
Similarly, we find the path lengths for all other neighbors (vertices 3 and 6).
All neighbors of vertex 1 are checked. The current minimum distance to peak 1 is considered final and cannot be revised. Vertex 1 is marked as visited.
Second step
Step 1 of the algorithm is repeated. Again we find the “nearest” of the unvisited vertices. This is vertex 2 with label 7.
Again we try to reduce the labels of the neighbors of the selected vertex, trying to pass through the 2nd vertex into them. The neighbors of vertex 2 are vertices 1, 3 and 4.
Vertex 1 has already been visited. The next neighbor of vertex 2 is vertex 3, since it has the minimum label of the vertices marked as not visited. If you go to it through 2, then the length of such a path will be equal to 17 (7 + 10 = 17). But the current label of the third vertex is 9, and 9< 17, поэтому метка не меняется.
Another neighbor of vertex 2 is vertex 4. If you go to it through 2nd, then the length of such a path will be equal to 22 (7 + 15 = 22). Since 22<10000, устанавливаем метку вершины 4 равной 22.
All neighbors of vertex 2 have been viewed, mark it as visited.
Third step
We repeat the algorithm step, selecting vertex 3. After “processing” it, we obtain the following results. 
Fourth step
Fifth step
Sixth step
Thus, the shortest path from vertex 1 to vertex 5 is the path through the vertices 1 — 3 — 6 — 5
, since in this way we gain a minimum weight of 20.
Let's start deriving the shortest path. We know the path length for each vertex, and now we will consider the vertices from the end. We consider the final vertex (in this case, the vertex 5
), and for all the vertices with which it is connected, we find the path length by subtracting the weight of the corresponding edge from the path length of the final vertex.
Yes, the top 5
has path length 20
. It is connected to the peaks 6
And 4
.
For the top 6
we get the weight 20 - 9 = 11 (matched).
For the top 4
we get the weight 20 - 6 = 14 (did not match).
If as a result we get a value that matches the path length of the vertex in question (in this case, the vertex 6
), then it was from it that the transition to the final vertex was made. We mark this peak on the desired path.
Next, we determine the edge through which we got to the vertex 6
. And so on until we get to the beginning.
If, as a result of such a traversal, at some step we have the same values for several vertices, then we can take any of them - several paths will have the same length.
Implementation of Dijkstra's algorithm
A square matrix is used to store the weights of the graph. The row and column headers contain the vertices of the graph. And the weights of the graph arcs are placed in the internal cells of the table. The graph does not contain loops, so the main diagonal of the matrix contains zero values.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Implementation in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
{
int a; // connection matrix
int d; // minimum distance
int v; // visited vertices
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251" );
system("cls" );
// Initialize the connection matrix
for (int i = 0; i
a[i][i] = 0;
for (int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Output the connection matrix
for (int i = 0; i
for (int j = 0; j
printf("\n" );
}
//Initialization of vertices and distances
for (int i = 0; i
d[i] = 10000;
v[i] = 1;
}
d = 0;
// Algorithm step
do (
minindex = 10000;
min = 10000;
for (int i = 0; i
if ((v[i] == 1) && (d[i]
min = d[i];
minindex = i;
}
}
// Add the found minimum weight
// to the current weight of the vertex
// and compare with the current minimum weight of the vertex
if (minindex != 10000)
{
for (int i = 0; i
if (a[i] > 0)
{
temp = min + a[i];
if (temp< d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
) while (minindex< 10000);
// Print shortest distances to vertices
printf( "\nShortest distances to vertices:\n");
for (int i = 0; i
// Restore path
int ver; // array of visited vertices
int end = 4; // end vertex index = 5 - 1
ver = end + 1; // starting element - ending vertex
int k = 1; // index of the previous vertex
int weight = d; // weight of the final vertex
while (end != begin_index) // until we reach the initial vertex
{
for (int i = 0; i
if (a[i] != 0) // if there is a connection
{
int temp = weight - a[i]; // determine the weight of the path from the previous vertex
if (temp == d[i]) // if the weight matches the calculated one
{ // this means there was a transition from this vertex
weight = temp; // save the new weight
end = i; // save the previous vertex
ver[k] = i + 1; // and write it to an array
k++;
}
}
}
// Output the path (the starting vertex ended up at the end of an array of k elements)
printf( "\nOutput the shortest path\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
return 0;
}
Execution result
Back:
Dijkstra's algorithm is designed to find the shortest path between vertices in an undirected graph.
The idea of the algorithm is as follows: first, we choose the path to the initial vertex equal to zero and add this vertex to the set of already selected ones, the distance from which to the remaining unselected vertices is determined. At each next stage, we find the next selected vertex, the distance to which is the smallest, and connected by an edge to some vertex from the set of unselected ones (this distance will be equal to the distance to the selected vertex plus the length of the edge).
Example 1. Find the shortest path on a graph from a vertex L to the top D(Fig. 10.7).
Rice. 10.7.
Let's write the algorithm as a sequence of steps (Table 10.1). Step 1. Determine the distances from the initial vertex L before everyone else.
Table 10.1
Dijkstra's method (first step)
|
Selected |
Path to the selected peak |
Unselected vertex |
|||||||
Step 2. Select the shortest distance from L before IN; found vertex IN accepted as the newly selected one. The found smallest distance is added to the lengths of the edges from the new vertex IN before everyone else. Select the minimum distance from IN before N. New peak N accepted as selected (Table 10.2).
Table 10.2
Dijkstra's method (second step)
|
Selected |
Path to the selected peak |
Unselected vertex |
|||||||
For clarity, in the future, instead of the sign oo, we will put the sign “-”.
Step 3. Determine the distances from the vertex N l about all the remaining ones (except L And IN), as shown in table. 10.3.
Table 10.3
Dijkstra's method (third step)
|
Selected |
Path to the selected peak |
Unselected vertex |
|||||||
Distance from top L through the top N to peaks G equals 18 conventional units. This distance is greater than the distance LB+BG= 16 conventional units, as a result of which it is not taken into account further. Continuing similar constructions, we compile a table. 10.4. Thus, the length of the shortest path between the vertices has been found L And D(44 conventional units).
The path trajectory is determined as follows. We perform a reverse scan from the final vertex to the starting one. We look through the column corresponding to the vertex from bottom to top and record the first appearance of the minimum value. In the column corresponding to the vertex D, for the first time the minimum length of 44 conventional units appeared at the bottom in the fourth line. This line indicates the vertex S, to which to go, i.e. Next we need to consider the column corresponding to the vertex S.
Table 10.4
|
Selected vertex |
Path to the selected peak |
Unselected vertex |
|||||||
In this column, the minimum length equal to 27 conventional units indicates the next vertex G, to which one should go, etc. Thus, we get the path trajectory: (L, B, G, S, D).
Example 8. Find the shortest path on the graph between the 1st and 7th vertices (Fig. 10.8).
We determine (Table 10.5) the next selected vertex, the distance to which is the smallest and connected by an edge to one of the vertices belonging to the set of unselected ones (this distance will be equal to the distance to the selected vertex plus the length of the edge).
Rice. 10.8. Graph (A) and its corresponding adjacency matrix (b)
Tabular implementation of Dijkstra's method
Table 10.5
|
Selected |
Path to the selected peak |
Unselected vertex |
||||||
|
at 6 |
||||||||
We perform a reverse scan from the final vertex to the starting one.
We look through the column corresponding to the vertex from bottom to top and record the first appearance of the minimum value. The shortest path will be equal to (V 7 - V 5 - V 2 - U ().
And CONTROL QUESTIONS
- 1. What is the theoretical complexity of the algorithms: decision tree construction, dynamic programming and Dijkstra?
- 2. What is the peculiarity of using a decision tree for a directed and undirected graph?
- 3. In solving what applied problems are algorithms used to determine the shortest distances between given vertices in a graph?
- 4. Can Dijkstra’s algorithm discussed in this work be applied to determining the shortest distance in a directed graph?
- 5. How does Dijkstra's algorithm work?
- 6. How does the dynamic programming algorithm work in relation to the problem of determining the shortest distances between vertices in a graph?
Dijkstra's algorithm is a graph algorithm that finds the shortest path between two given vertices in a graph with non-negative arc lengths. The task of calculating the shortest path from a given vertex to all others is also often posed. The algorithm is widely used in programming, for example, it is used in routing protocols.
Description
The input of the algorithm is a weighted directed graph with arcs of non-negative weight. The output is a set of shortest paths from a given vertex to others.
At the beginning, the distance for the initial vertex is assumed to be zero, and the distances to all others are assumed to be infinite. An array of flags indicating whether the vertex has been passed is filled with zeros. Then, at each step of the cycle, a vertex with a minimum distance to the original one and a flag equal to zero is searched. A flag is set for it and all neighboring vertices are checked. If the previously calculated distance from the original vertex to the one being checked is greater than the sum of the distance to the current vertex and the length of the edge from it to the vertex being checked, then the distance to the vertex being checked is equated to the distance to the current + edge from the current to the one being checked. The cycle ends when the flags of all vertices become equal to 1, or when the distance to all vertices with a flag of 0 is infinite. The last case is possible if and only if the graph is disconnected.
Dijkstra's algorithm in pseudocode
Entrance: WITH: array of real – matrix of graph arc lengths; s is the vertex from which the shortest path is sought and t is the vertex to which it is sought.
Output: vectors T: array of real; and N: array of 0..r. If the top v lies on the shortest path from s To t, That T[v]- length of the shortest path from s To y; Well] - the peak immediately preceding at on the shortest path.
Н – an array in which vertex n corresponds to vertex m, the previous one on the way to n from s.
T is an array in which vertex n corresponds to the distance from it to s.
X is an array in which vertex n corresponds to 1 if the path to it is known, and 0 if not.
initializing arrays:
for v from 1 to R do
T[v]: = ∞ (shortest path unknown)
X[v]: = 0 (all vertices are unmarked)
H[s]: = 0 ( s nothing precedes)
T[s]: = 0 (shortest path has length 0...)
X[s]: = 1 (...and he is famous) v : = s (current top)
M: (update notes)
for and ∈ G( And) do
if X[i] = 0 & T[i]> T[v] + C then
T[i]: = T[v] + C(found a shorter route from s V And through v }
H[u]:= v(remember it)
m: = ∞
v : = 0
(finding the end of the shortest path)
for And from 1 to p do
if X[u] = 0 &T[u]< t then
v:= u;
m:= T[u](top v ends the shortest path from s
if v = 0 then
stop (no path from s V t) end if
if v= t then
stop ( found the shortest path from s V t) end if
X[v]: = 1 ( found the shortest path from s V v ) goto M
Rationale
To prove the correctness of Dijkstra's algorithm, it is enough to note that each time the body of the loop starting with label M is executed, v a vertex is used for which the shortest path from the vertex is known s. In other words, if X[v] = 1, then T[v] = d(s,v) , and all vertices on the path (s,v) defined by the vector H have the same property, that is
Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.
Indeed (by induction), the first time as v a vertex s is used for which the shortest path is empty and has length 0 (non-empty paths cannot be shorter because the lengths of the arcs are non-negative). Let T[u] = d(s,u) for all previously marked vertices And. Consider the newly labeled vertex v, which is selected from the condition T[v] = min T[i]. Note that if the path passing through the marked vertices is known, then the shortest path is thereby known. Let us assume (by contradiction) that T[v]> d(s, v), that is, the found path leading from s V v, is not the shortest. Then there must be unmarked vertices on this path. Consider the first vertex w on this path, such that T[w] = 0.We have: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.
Time complexity
The complexity of Dijkstra's algorithm depends on the method of finding an unvisited vertex with the minimum distance to the original one, the method of storing the set of unvisited vertices, and the method of updating labels. Let n be the number of vertices, and let m be the number of edges in the graph. Then in the simplest case, when to search for a vertex with the minimum distance to the original vertex, the entire set of vertices is scanned, and an array is used to store the distances, the running time of the algorithm is O(n 2). The main loop is executed about n times, in each of them about n operations are spent on finding the minimum. Cycles through the neighbors of each visited vertex require a number of operations proportional to the number of edges m (since each edge occurs exactly twice in these cycles and requires a constant number of operations). Thus, the total running time of the algorithm is O(n 2 +m), but since m is much less than n(n-1), the final result is O(n 2).
For sparse graphs (that is, those for which m is much less than n²), unvisited vertices can be stored in the binary heap, and distance values can be used as a key. Since the loop is executed about n times, and the number of relaxations (label changes) is no more than m, the running time of such an implementation is O(nlogn+mlogn)
Example
Calculation of distances from vertex 1 based on traversable vertices:
The shortest path is considered using some mathematical object called a graph. Search shortest path is conducted between two given vertices in the graph. The result is a path, that is, a sequence of vertices and edges incident to two neighboring vertices, and its length.
Let's look at three of the most efficient algorithm finding shortest path:
- Dijkstra's algorithm;
- Floyd's algorithm;
- search algorithms.
These algorithms are easily executed with a small number of vertices in the graph. As their number increases, the search problem shortest path becomes more complicated.
Dijkstra's algorithm
This algorithm is a graph algorithm, which was invented by the Dutch scientist E. Dijkstra in 1959. The algorithm finds the shortest distance from one of the vertices of the graph to all the others and works only for graphs without edges of negative weight.
Each vertex is assigned a weight - this is the weight of the path from the initial vertex to this one. Also, each vertex can be selected. If a vertex is selected, then the path from it to the initial vertex is the shortest; if not, then it is temporary. Traversing the graph, the algorithm calculates the route for each vertex, and, if it turns out to be the shortest, selects the vertex. The weight of this vertex becomes the weight of the path. For all neighbors of a given vertex, the algorithm also calculates the weight , but under no circumstances selects them. The algorithm finishes its work having reached the final vertex, and the weight shortest path becomes the weight of the final vertex.
Dijkstra's algorithm
Step 1. All vertices, except the first one, are assigned a weight equal to infinity, and the first vertex is assigned a weight equal to 0.
Step 2. All vertices are not selected.
Step 3. The first vertex is declared current.
Step 4. The weight of all unselected vertices is recalculated using the formula: the weight of an unselected vertex is the minimum number of the old weight of this vertex, the sum of the weight of the current vertex and the weight of the edge connecting the current vertex to the unselected one.
Step 5. Among the unselected vertices, the vertex with the minimum weight is searched. If one is not found, that is, the weight of all vertices is equal to infinity, then the route does not exist. Therefore, the output is . Otherwise, the found vertex becomes the current one. She stands out.
Step 6. If the current vertex is the final one, then the path is found, and its weight is the weight of the final vertex.
Step 7. Go to step 4.
In software implementation Dijkstra's algorithm Let's construct a set S of vertices for which the shortest paths from the initial vertex are already known. At each step, one of the remaining vertices is added to the set S, the distance to which from the initial vertex is less than for the other remaining vertices. In this case, we will use the array D, in which the lengths are written shortest paths for each vertex. When the set S contains all the vertices of the graph, then the array D will contain the lengths shortest paths from the starting vertex to each vertex.
In addition to the indicated arrays, we will use a matrix of lengths C, where element C is the length of the edge (i,j), if there is no edge, then its length is assumed to be equal to infinity, that is, greater than any actual length of the edges. In fact, the matrix C is adjacency matrix, in which all zero elements are replaced by infinity.
To determine the