Dijkstra's algorithm is a graph algorithm that finds the shortest path between two given vertices in a graph with non-negative arc lengths. Also, the task of calculating the shortest path from a given vertex to all the others is often posed. The algorithm is widely used in programming, for example, it is used by 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 the others are considered to be infinite. An array of flags indicating whether the vertex has been passed is filled with zeros. Then, at each step of the loop, a vertex with a minimum distance to the initial one and a flag equal to zero is searched for. A flag is set for it and all neighboring vertices are checked. If the previously calculated distance from the source vertex to the checked vertex is greater than the sum of the distance to the current vertex and the length of the edge from it to the checked vertex, then the distance to the checked vertex is equated to the distance to the current one + the edge from the current to the checked one. The loop ends when the flags of all vertices become equal to 1, or when the distance to all vertices with flag 0 is infinite. The latter case is possible if and only if the graph is disconnected.

Dijkstra's algorithm in pseudocode

Entrance: FROM: array of real – matrix of lengths of graph arcs; 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 H: array of 0..r. If top v lies on the shortest path from s to t, then T[v]- shortest path length from s to y; Well] - peak immediately preceding at on the shortest path.

H is 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.

array initialization:

for v from 1 to R do

T[v]: = ∞ (shortcut unknown)

X[v]: = 0 (all vertices are unchecked)

H[s]: = 0 ( s nothing comes before)

T[s]:= 0 ( shortest path has length 0...)

X[s]:= 1 ( ...and he's known ) v : = s (current top)

M: (notes update)

for and ∈ G( and) do

if X[i] = 0 & T[u]> T[v] + C then

T[u]: = T[v] + C(found a shorter path from s in 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 way out s in t) end if

if v= t then

stop ( found the shortest path from s in t) end if

X[v]: = 1 ( found the shortest path from s in v ) goto M

Rationale

To prove the correctness of Dijkstra's algorithm, it suffices to note that for each execution of the loop body beginning with the label M, as 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, i.e.

Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.

Indeed (by induction), the first time as v the vertex s is used, for which the shortest path is empty and has length 0 (non-empty paths cannot be shorter, because the arc lengths are non-negative). Let T[u] = d(s,u) for all previously labeled vertices and. Consider the newly labeled vertex v, which is selected from the condition T[v] = min T[u]. Note that if the path passing through the labeled vertices is known, then the shortest path is known. Assume (on the contrary) that T[v] > d(s, v), that is, the found path leading from s in v, is not the shortest. Then there must be unlabeled 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 how to find an unvisited vertex with the minimum distance to the original one, how to store the set of unvisited vertices, and how to update 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 the entire set of vertices is searched to find the vertex with the minimum distance to the original vertex, and an array is used to store the distances, the algorithm's running time 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. Cycling through the neighbors of each visited vertex takes 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), it ends up being O(n 2).

For sparse graphs (that is, those for which m is much less than n²), unvisited vertices can be stored in a binary heap, and distance values ​​\u200b\u200bare used as a key. Since the loop is executed about n times, and the number of relaxations (label changes) is not more than m, the running time of such an implementation is O(nlogn+mlogn)

Example

Calculation of distances from vertex 1 by traversable vertices:

Consider 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 paths from the city center to each city in the area.

To solve this problem, you can use Dijkstra's algorithm- an algorithm on graphs, invented by the Dutch scientist E. Dijkstra in 1959. Finds the shortest distance from one of the graph's vertices to all the others. Works only for graphs without edges of negative weight.

Let it be required to find the shortest distances from the 1st vertex to all the others.

The circles denote the vertices, the lines denote the paths between them (the edges of the graph). The numbers of vertices are indicated in the circles, their weight is indicated above the edges - the length of the path. Next to each vertex, a red label is marked - the length of the shortest path to this vertex from vertex 1.

The label of the vertex 1 itself is assumed to be 0, the labels of the remaining vertices are 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. Vertices 2, 3, and 6 are its neighbors. We bypass 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 node 1 are checked. The current minimum distance to summit 1 is considered final and is not subject to revision. 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 labeled 7.

Again we try to reduce the labels of the neighbors of the selected vertex, trying to pass through them through the 2nd vertex. Vertex 2's neighbors 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 unvisited. 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 we go to it through the 2nd one, 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, so we mark it as visited.

Third step

We repeat the step of the algorithm by selecting vertex 3. After its “processing”, we get the following results.

Fourth step

Fifth step

sixth step

Thus, the shortest path from vertex 1 to vertex 5 will be the path through the vertices 1 — 3 — 6 — 5 , since in this way we gain a minimum weight of 20.

Let's take a look at the shortest path. We know the length of the path for each vertex, and now we will consider the vertices from the end. Consider the final vertex (in this case, the vertex 5 ), and for all 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, top 5 has a path length 20 . She's connected to the top 6 and 4 .
For the top 6 get the weight 20 - 9 = 11 (matched).
For the top 4 get the weight 20 - 6 = 14 (didn't 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 vertex 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 graph weights. The vertices of the graph are in the headings of the rows and columns. 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; // matrix of connections
int d; // minimum distance
intv; // visited vertices
int temp, miniindex, min;
int begin_index = 0;
system("chcp 1251" );
system("cls" );
// Initialization of the relationship matrix
for (int i = 0; i {
a[i][i] = 0;
for (int j = i + 1; j printf( "Enter distance %d - %d: ", i + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Display the relationship matrix
for (int i = 0; i {
for (int j = 0; j printf("%5d " , a[i][j]);
printf("\n");
}
//Initialize 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 the vertex has not yet been visited and the weight is less than min
if ((v[i] == 1) && (d[i] { // Reassign values
min = d[i];
miniindex=i;
}
}
// Add the found minimum weight
// to the current vertex weight
// and compare with the current minimum vertex weight
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);
// Display the shortest distances to the vertices
printf( "\nShortest distances to vertices: \n");
for (int i = 0; i printf("%5d " , d[i]);

// Restore Path
intver; // array of visited vertices
int end = 4; // end vertex index = 5 - 1
ver = end + 1; // start element - end vertex
int k = 1; // index of the previous peak
int weight = d; // end vertex weight

while (end != begin_index) // until we reach the starting vertex
{
for (int i = 0; i // look at all vertices
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
{ // it means that there was a transition from this vertex
weight = temp; // store the new weight
end = i; // save the previous vertex
ver[k] = i + 1; // and write it to an array
k++;
}
}
}
// Displaying the path (the starting vertex is at the end of the array of k elements)
printf( "\nOutput shortest path\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
return 0;
}

Execution result


Back:

Given a directed or undirected weighted graph with vertices and edges. The weights of all edges are non-negative. Some starting vertex is specified. It is required to find the lengths of the shortest paths from a vertex to all other vertices, and also provide a way to output the shortest paths themselves.

This problem is called the single-source shortest paths problem.

Algorithm

This describes the algorithm proposed by the Dutch researcher Dijkstra(Dijkstra) in 1959

Let's get an array in which for each vertex we will store the current length of the shortest path from to . Initially , and for all other vertices, this length is equal to infinity (when implemented on a computer, usually a sufficiently large number is chosen as infinity, obviously greater than the possible length of the path):

In addition, for each vertex we will store whether it is still labeled or not, i.e. let's get a boolean array. Initially, all vertices are unlabeled, i.e.

Dijkstra's algorithm itself consists of iterations. At the next iteration, the vertex with the smallest value among those not yet labeled is selected, i.e.:

(It is clear that at the first iteration the starting vertex will be selected.)

The vertex selected in this way is marked marked. Further, at the current iteration, from the vertex, relaxation: all edges outgoing from vertex are looked through, and for each such vertex the algorithm tries to improve the value of . Let the length of the current edge be , then in the form of a code, the relaxation looks like:

This is where the current iteration ends, the algorithm proceeds to the next iteration (again, the vertex with the smallest value is selected, relaxations are performed from it, etc.). In this case, in the end, after iterations, all the vertices of the graph will become labeled, and the algorithm completes its work. It is claimed that the found values ​​are the required lengths of the shortest paths from to .

It is worth noting that if not all vertices of the graph are reachable from the vertex , then the values ​​for them will remain infinite. It is clear that the last few iterations of the algorithm will just select these vertices, but these iterations will not produce any useful work (since an infinite distance cannot relax other, even infinite distances). Therefore, the algorithm can be immediately stopped as soon as a vertex with infinite distance is taken as the selected vertex.

Path restoration. Of course, one usually needs to know not only the lengths of the shortest paths, but also the paths themselves. Let us show how to store information sufficient for subsequent reconstruction of the shortest path from to any vertex. For this, the so-called ancestor array: an array that holds, for each vertex, the number of the vertex that is penultimate in the shortest path to the vertex. This uses the fact that if we take the shortest path to some vertex , and then remove the last vertex from this path, then we get a path ending in some vertex , and this path will be the shortest for vertex . So, if we have this array of ancestors, then the shortest path can be restored from it, simply each time taking the ancestor from the current vertex until we get to the starting vertex - this way we get the desired shortest path, but written in reverse order. So the shortest path to the top is:

It remains to understand how to build this array of ancestors. However, this is done very simply: with each successful relaxation, i.e. when from the selected vertex there is an improvement in the distance to some vertex , we write that the vertex's ancestor is the vertex :

Proof

Main Statement, on which the correctness of Dijkstra's algorithm is based, is as follows. It is stated that after any vertex becomes marked, the current distance to it is already the shortest, and, accordingly, will not change anymore.

Proof we will produce by induction. For the first iteration, its validity is obvious - for the vertex we have , which is the length of the shortest path to it. Now let this assertion hold for all previous iterations, i.e. all already marked vertices; let us prove that it is not violated after the execution of the current iteration. Let be the vertex selected at the current iteration, i.e. the vertex that the algorithm is going to label. Let us prove that is really equal to the length of the shortest path to it (we denote this length by ).

Consider the shortest path to the top. It is clear that this path can be divided into two paths: , consisting only of marked vertices (at least the starting vertex will be in this path), and the rest of the path (it can also include marked vertices, but it always starts with an unmarked one). Denote by the first vertex of the path , and by the last vertex of the path .

Let us first prove our assertion for the vertex , i.e., let's prove the equality. However, this is almost obvious: after all, at one of the previous iterations, we chose a vertex and performed relaxation from it. Since (due to the very choice of the vertex ) the shortest path to is equal to the shortest path to plus the edge , then when the relaxation from is performed, the value will indeed be set to the required value.

Due to the non-negativity of the costs of the edges, the length of the shortest path (which, according to what has just been proved, is equal to ) does not exceed the length of the shortest path to the vertex . Considering that (after all, Dijkstra's algorithm could not find a shorter path than is generally possible), as a result, we obtain the following relations:

On the other hand, since both and and are unlabeled vertices, since it was the vertex that was chosen at the current iteration, and not the vertex , we obtain another inequality:

From these two inequalities we conclude the equality , and then from the relations found before, we obtain and:

Q.E.D.

Implementation

So, Dijkstra's algorithm consists of iterations, at each of which an unlabeled vertex with the smallest value is selected, this vertex is labeled, and then all edges outgoing from this vertex are looked through, and along each edge an attempt is made to improve the value at the other end of the edge.

The running time of the algorithm is the sum of:

With the simplest implementation of these operations, operations will be spent on finding a vertex, and operations on one relaxation, and the final asymptotics algorithm is:

Implementation:

const int INF = 1000000000 ; int main() ( int n; ... read n ... vector< vector < pair< int ,int >> > g(n); ... graph reading... int s = ...; // starting vertex vector< int >d(n, INF) , p(n) ; d[s] = 0; vector< char >u(n); for (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

Here the graph is stored in the form of adjacency lists: for each vertex, the list contains a list of edges emanating from this vertex, i.e. a list of pairs >, where the first element of the pair is the vertex that the edge leads to, and the second element is the weight of the edge.

5.4.3. The shortest path problem and Dijkstra's algorithm for solving it

Let a digraph be given G(V, E), each arc of which is assigned a number
called arc length.

Definition. Length path is the sum of the lengths of the arcs that make up this path. Shortest Path Problem put like this.

Option 1. Find the lengths of the shortest paths (paths of minimum length) and the paths themselves from a fixed vertex s to all other vertices of the graph.

Option 2. Find the lengths of the shortest paths and the paths themselves between all pairs of vertices in the given graph.

If the graph has arcs of negative length, the problem may not have solutions (it will lose its meaning). This is due to the fact that the graph may contain a contour of negative length. The presence of contours of negative length means that the length of the path can be made equal to
. And if there are no contours of negative length, then shortest paths exist, and any shortest path is a simple chain.

Note that if a shortest path exists, then any of its subpaths is also the shortest path between the corresponding vertices.

Dijkstra's algorithm for solving the shortest path problem.

The algorithm works with arcs of positive length and determines the shortest paths from a fixed vertex s to all other vertices of the graph. Let's label these vertices v 1 , v 2 ,…, v n .

Definition. Let's call the vertex u lying closer to the top s than top v if the length of the shortest path from s before u less than the length of the shortest path from s before v. We will say that the peaks u and v equidistant from the top s, if the lengths of the shortest paths from s before u and from s before v match.

Dijkstra's algorithm sequentially orders the vertices of a graph in terms of proximity to a vertex s and is based on the following basic principles.

If arc lengths are positive numbers, then

closest to s the top is herself. The length of the shortest path from s before s is 0;

closest to s vertex other than s, lies from s at a distance of one arc - the shortest of all arcs emerging from the vertex s;

any intermediate vertex of the shortest path from s up to some peak v lies closer to s than the end vertex v;

the shortest path to the next ordered vertex can only pass through already ordered vertices.

Let the algorithm have already ordered the vertices v 1 , v 2 … v k . Denote by
,
length of the shortest path to the top v i .

Consider all arcs of the original graph that start at one of the vertices of the set
and terminate at yet unordered vertices. For each such arc, for example
, calculate the sum
. This sum is equal to the length of the path from s in y, in which the top v i is the penultimate vertex, and the path from s in v i is the shortest of all paths connecting s and v i .

This determines the lengths of all paths from s to not yet ordered vertices, in which only vertices from among the intermediate vertices are k closest to s. Let the shortest of these paths end at the top w. Then w and eat
close to s vertex.

Technically, actions according to Dijkstra's algorithm are carried out using the apparatus of vertex labels. Vertex Label v denoted as
. Every label is a number equal to the length of some path from s before v. Labels are divided into temporary and permanent. At each step, only one label becomes permanent. This means that its value is equal to the length of the shortest path to the corresponding vertex, and this vertex itself is ordered. The number of the next ordered vertex is denoted by the letter R.

Description of the algorithm.

Step 1. (Initial setting). Put
and consider this label permanent. Put
,
and treat these labels as temporary. Put
.

Step 2 (general step). It repeats n times until all the vertices of the graph are sorted.

Recalculate Timestamp
any unordered vertex v i, which includes the arc leaving the vertex R, according to the rule

Select the vertex with the minimum timestamp. If there are several such vertices, choose any.

Let w- the vertex with the minimum timestamp. Read label
constant and put
.

It is convenient to arrange the steps of Dijkstra's algorithm in a table, each column of which corresponds to a vertex of the graph. The rows of the table correspond to the repetition of the common step.

Example. For the graph in Fig. 4. find the shortest paths from the vertices
to all other vertices of the graph. Edges mean two differently directed arcs of the same length.

Solution. In table. 1 labels of vertices at each step are written. Permanent marks are marked with a "+" sign. Let us describe in detail how vertex labels are calculated.

From vertex 1, arcs go out to vertices 2, 5, 6. Recalculate the labels of these vertices and fill in the second row of the table.

Vertex label 6 becomes permanent,
.

From vertex 6, arcs go out to still unordered vertices 2, 5, 8, 9. Recalculate their timestamps

Fill in row 3 of the table. The minimum of the timestamps is 3 (vertex label 9),
.

From vertex 9, arcs go out to the still unordered vertices 5, 8, 11, 12. Then

Fill in the fourth line of the table. In this line, two vertices - 2 and 12 have minimum timestamps equal to 4. First, let's order, for example, vertex 2. Then, at the next step, vertex 12 will be ordered.

Table 1

So,
.

From vertex 2, arcs go out to the still unordered vertices 3, 4, 5. Recalculate the timestamps of these vertices

Fill in row 5 of the table. The minimum of the timestamps is 4 (vertex label 12),
.

Fill in row 6 of the table. The minimum of the timestamps is 5 (vertex label 5),
.

Fill in row 7 of the table. Vertex label 8 becomes constant (it is equal to 5),
.

Vertex 11 is ordered.

From vertex 11, arcs go out to unordered vertices 7, 10. Recalculate the timestamps of these vertices

Vertex 4 gets a permanent label.

From vertex 4, arcs go out to unordered vertices 3, 7. Recalculate timestamps

Arrange top 3.

Fill in line 12 of the table. At this step, we order the last unordered vertex 10.

Building a tree of shortest paths.

A shortest path tree is a directed tree rooted at a vertex. S . All paths in this tree are the shortest paths for this graph.

The shortest path tree is built according to the table, vertex by vertex is included in it in the order in which they received permanent labels. The root is the first node to be included in the tree. S .

Let's build a tree of shortest paths for our example.

First, we include the root, vertex 1, in the tree. Then, the arc (1,6) is included in the tree. Vertex 9 was ordered next, the length of the shortest path to which is equal to 3. The first time the number 3 appeared in the third row, which was filled with
. Therefore, vertex 6 is the penultimate vertex of the shortest path to vertex 9. We include the arc (6,9) of length 1 in the tree.

Then vertex 2 was ordered with the shortest path length equal to 4. This number first appeared in the third row, which was filled with
. Consequently, the shortest path to the second vertex passes along the arc (6,2). We include the arc (6,2) of length 2 in the tree.

Next, vertex 12 was ordered,
. The first time the number 4 appears in the fourth line, which was filled in when
. The arc (9,12) of length 1 is included in the tree. The complete tree of shortest paths is shown in fig. 5.

Dijkstra's algorithm can fail if the graph has arcs of negative length. So, looking for the shortest paths from the top s =1 for the graph in fig. 6, the algorithm will first order node 3, then node 2, and finish. Moreover, this shortest path to vertex 3, from the point of view of Dijkstra's algorithm, is an arc (1,3) of length 3.

In fact, the shortest path to vertex 3 consists of arcs (1,2) and (2,3), the length of this path is 5+(-3)=2.

Due to the presence of an arc (2,3) of negative length –3, the following basic principles were violated:

closest to s the vertex lies at a distance of two arcs from it, and not one;

the intermediate vertex of the shortest path 1-2-3 (vertex 2) lies farther from vertex 1 (distance 5) than the final vertex of path 3.

Therefore, the presence of arcs of negative length complicates the solution of the shortest path problem and requires the use of more complex algorithms than Dijkstra's algorithm.

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 working principle of Dijkstra's 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.

For example, take the following directed graph G:

We can represent this graph as a matrix C:

Let's 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 through all the vertices of the graph and assigns labels to them, which are the known minimum distance from the source vertex to a particular vertex. Let's consider this algorithm with an example.

Let's assign a label equal to 0 to the 1st vertex, 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 minimum label (now it is vertex 1) and consider all vertices to which from the vertex W there is a path that does not contain mediator vertices. We assign a label to each of the considered vertices equal to the sum of the label W and the length of the paths from W to the vertex under consideration, but only if the resulting sum is less than the previous value of the label. If the amount is not less, then we leave the previous label unchanged.

After we have considered 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 the 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, then it doesn't matter which one we choose as W.

We choose vertex 2. But there is no outgoing path from it, so we immediately mark this vertex as visited and move on to the next vertex with the minimum label. This time only vertex 5 has the minimum label. Consider all vertices to which there are direct paths from 5, but which have not yet been 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 value of the label with the resulting sum.

Based on the picture, we can see that the labels of the 3rd and 4th vertices have become smaller, that is, a shorter route was found to these vertices from the source vertex. Next, mark the 5th vertex as visited and select the next vertex that has the minimum label. We repeat all the above actions as long as there are unvisited vertices.

After completing all the steps, we get the following result:

There is also a vector P, based on which you can build 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 source vertex (in our case, P = (1, 1, 1, 1, 1)). Further, at the stage of recalculating the label value for the considered vertex, if the label of the considered vertex 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", with W=1. Further, at W=5, the label of the 3rd vertex has changed to "20", therefore we will write the value into the vector P - P=5. Also, at W=5, the value of the label at the 4th vertex has changed (it was "50", it became "40"), so you need to assign the value W - P=5 to the 4th element of the vector P. As a result, we get the vector Р = (1, 1, 5, 5, 1).

Knowing that each element of the vector P contains the last intermediate vertex on the path between the source and the final vertex, we can get the shortest route itself.