You get a bonus - 1 coin for daily activity. Now you have 1 coin

Dijkstra's Algorithm

Lecture



The algorithm of the Dutch scientist Edsger Dijkstra finds all the shortest paths from one initially defined vertex of the graph to all the others. With it, with all the necessary information, you can, for example, find out which sequence of roads is better to use to get from one city to each of many others, or to which countries it is more profitable to export oil and the like. The disadvantage of this method is the impossibility of processing graphs with negative weight edges, i.e. if, for example, some system provides routes that are unprofitable for your company, then you should use a method other than Dijkstra’s algorithm to work with it.

For the software implementation of the algorithm, we need two arrays: a logical visited - to store information about the visited vertices and a numerical distance in which the shortest paths will be entered. So, there is a graph G = (V, E). Each of the vertices in the set V is initially marked as not visited, that is, the elements of the visited array are set to false. Since the most profitable paths are only to be found, each element of the distance vector records a number that is obviously greater than any potential path (usually this number is called infinity, but the program uses, for example, the maximum value of a particular data type). The vertex s is selected as the starting point and the zero path is assigned to it: distance [s] = 0, since there is no edge from s to s (the method does not provide loops). Further, all adjacent vertices (which have an edge from s) are located (let t and u be such) and are investigated in turn, namely, the cost of the route from s is alternately calculated for each of them:

  • distance [t] = distance [s] + weight of the s and t edges;
  • distance [u] = distance [s] + of the weight s and u edges.

But it is quite probable that there are several paths to one or another vertex from s, so the price of the path to such a vertex in the distance array will have to be revised, then the highest (non-optimal) value is ignored, and the smallest is assigned to the vertex.

After processing the vertices adjacent to s, it is marked as visited: visited [s] = true, and that vertex becomes active, the path from s to which is minimal. Suppose the path from s to u is shorter than from s to t, therefore, the vertex u becomes active and its neighbors are investigated in the above manner, with the exception of the vertex s. Further, u is marked as passed: visited [u] = true, the vertex t becomes active, and the whole procedure is repeated for it. Dijkstra’s algorithm continues until all the vertices accessible from s are examined.

Now, on a specific graph, let us follow the operation of the algorithm, find all the shortest paths between the source and all the other vertices. The size (number of edges) of the graph shown below is 7 (| E | = 7), and the order (number of vertices) is 6 (| V | = 6). This is a weighted graph, each numerical value is assigned to each of its edges, so the route value is not necessarily determined by the number of edges lying between a pair of vertices.

Dijkstras Algorithm

From all the vertices in the set V, we choose one, the one from which it is necessary to find the shortest paths to the other available vertices. Let vertex 1 be such. The length of the path to all vertices except the first is initially equal to infinity, and to it is 0, since the graph has no loops.

Dijkstras Algorithm

Vertex 1 has exactly 3 neighbors (vertices 2, 3, 5), and to calculate the length of the path to them, add the weight of the arcs lying between the vertices: 1 and 2, 1 and 3, 1 and 5 with the value of the first vertex (with zero) :

  • 2 ← 1 + 0
  • 3 ← 4 + 0
  • 5 ← 2 + 0

As already noted, the resulting values ​​are assigned to the vertices, only if they are “better” (less) than those that appear at the moment. And since each of the three numbers is less than infinity, they become new values ​​that determine the length of the path from vertex 1 to vertices 2, 3, and 5.

Dijkstras Algorithm

Further, the active vertex is marked as visited, the status of “active” (red circle) goes to one of its neighbors, namely, to peak 2, since it is closest to the previously active peak.

Dijkstras Algorithm

At vertex 2 there is only one not considered neighbor (vertex 1 is marked as visited), the distance to which is 9, but we need to calculate the length of the path from the source vertex, for which we add the value assigned to vertex 2 with the weight of the arc from it to vertex 4 :

  • 4 ← 1 + 9

The condition of “brevity” (10 <∞) is fulfilled, therefore, vertex 4 receives a new value of the path length.

Dijkstras Algorithm

Vertex 2 ceases to be active, as well as vertex 1 is removed from the list of not visited. Now the neighbors of vertex 5 are examined in the same way, and the distance to them is calculated. Dijkstras Algorithm

When it comes to inspecting the neighbors of vertex 3, then it is important not to be mistaken, since vertex 4 has already been investigated and the distance of one of the possible paths from the source to it has been calculated. If we move to it through vertex 3, then the path will be 4 + 7 = 11, and 11> 10, so the new value is ignored, the old one remains.

Dijkstras Algorithm The situation is similar with vertex 6. The value of the closest path to it from vertex 1 is 10, and it turns out only if you go through vertex 5. Dijkstras Algorithm When all the vertices of the graph, or all those that are accessible from the source, will be marked as visited, then the work of the Dijkstra algorithm will end, and all the paths found will be shortest. So, for example, a list of the most optimal distances lying between vertex 1 and all other vertices of the graph under consideration will look like:

1 → 1 = 0
1 → 2 = 1
1 → 3 = 4
1 → 4 = 10
1 → 5 = 2
1 → 6 = 10

In the program that finds the nearest path between the vertices using the Dijkstra method, the graph will be represented as a non-binary adjacency matrix. Instead of units, the weights of the edges will be set in it, the function of the zeros will remain the same: to show between which vertices there are no edges or they are, but negatively directed.

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include "stdafx.h"
#include
using namespace std;
const int V = 6;
// Dijkstra's algorithm
void Dijkstra (int GR [V] [V], int st)
{
int distance [V], count, index, i, u, m = st + 1;
bool visited [V];
for (i = 0; i {
distance [i] = INT_MAX; visited [i] = false;
}
distance [st] = 0;
for (count = 0; count {
int min = INT_MAX;
for (i = 0; i if (! visited [i] && distance [i] <= min)
{
min = distance [i]; index = i;
}
u = index;
visited [u] = true;
for (i = 0; i if (! visited [i] && GR [u] [i] && distance [u]! = INT_MAX &&
distance [u] + GR [u] [i] distance [i] = distance [u] + GR [u] [i];
}
cout << "The cost of the path from the initial vertex to the rest: \ t \ n";
for (i = 0; i cout << m << ">" << i + 1 << "=" << distance [i] << endl;
else cout << m << ">" << i + 1 << "=" << "route not available" << endl;
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
int start, GR [V] [V] = {
{0, 1, 4, 0, 2, 0},
{0, 0, 0, 9, 0, 0},
{4, 0, 0, 7, 0, 0},
{0, 9, 7, 0, 0, 2},
{0, 0, 0, 0, 0, 8},
{0, 0, 0, 0, 0, 0}};
cout << "Start Vertex >>"; cin >> start;
Dijkstra (GR, start-1);
system ("pause >> void");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

program DijkstraAlgorithm;
uses crt;
const V = 6; inf = 100,000;
type vektor = array [1..V] of integer;
var start: integer;
const GR: array [1..V, 1..V] of integer = (
(0, 1, 4, 0, 2, 0),
(0, 0, 0, 9, 0, 0),
(4, 0, 0, 7, 0, 0),
(0, 9, 7, 0, 0, 2),
(0, 0, 0, 0, 0, 8),
(0, 0, 0, 0, 0, 0));
{Dijkstra algorithm}
procedure Dijkstra (GR: array [1..V, 1..V] of integer; st: integer);
var count, index, i, u, m, min: integer;
distance: vektor;
visited: array [1..V] of boolean;
begin
m: = st;
for i: = 1 to V do
begin
distance [i]: = inf; visited [i]: = false;
end;
distance [st]: = 0;
for count: = 1 to V-1 do
begin
min: = inf;
for i: = 1 to V do
if (not visited [i]) and (distance [i] <= min) then
begin
min: = distance [i]; index: = i;
end;
u: = index;
visited [u]: = true;
for i: = 1 to V do
if (not visited [i]) and (GR [u, i] <> 0) and (distance [u] <> inf) and
(distance [u] + GR [u, i] distance [i]: = distance [u] + GR [u, i];
end;
write ('The cost of the path from the initial vertex to the rest:'); writeln;
for i: = 1 to V do
if distance [i] <> inf then
writeln (m, '>', i, '=', distance [i])
else writeln (m, '>', i, '=', 'route unavailable');
end;
{main program block}
begin
clrscr;
write ('Start vertex >>'); read (start);
Dijkstra (GR, start);
end.

created: 2014-11-30
updated: 2021-12-15
132936



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments

Никита
04-12-2021
Здравствуйте. Довольно интересно изложен теоретический материал, да еще и с программным кодом. Хотел бы выразить благодарность, эта статья мне очень помогли. Буквально недавно изучил еще один довольно интересный алгоритм: https://www.mathros.net.ua/znahodzhennja-najkorotshyh-shljahiv-v-grafi-metodom-shimbella.html Не могли бы Вы набросать программный код, реализующий именно этот алгоритм (если можно в среде с++). В любом случае, спасибо за Ваши старания. Буду дальше активным читателем ваших материалов. С уважением, Никита.
Катя
04-12-2021
в той статье есть блок схема, по ней легко написать реализацию программы
Никита
05-12-2021
Блок-схема то есть, но исходя из того, что среду с++ только начал изучать, с реализацией пока туговато. Ладно, спасибо за оперативность. Предется кодировать самому. Потрачу чуть больше времени, однако приобрету немного опыта.

To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms