C++

Forum

 
Dijkstras explanation needed

HeavyDrugs (7)
Hello, I've been trying to understand dijkstras algorithm, but I'm stuck.
Could someone explain this part to me? Thanks.

Here's the whole code.
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
104
105
106
107
108
 
#include <iostream>

void dijakstra(int, int,int[][6]);
	
void print(int[], int, int);

//declare your stuff in main
	
int main() {

	int matrix[6][6] = { {0, 39, 999, 80, 999, 50},
				   {999, 999, 999, 35, 999, 20},
				   {999, 40, 999, 15, 999, 999},
				   {999, 999, 999, 999, 34, 47},
				   {999, 999, 20, 999, 999, 999},
				   {999, 999, 999, 999, 3, 999} 
	};
	
	/*
	std::cout << "Iveskite svorius" << std::endl;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			
			if (j == i) {
				continue;
			}
			
			std::cin >> matrix[i][j];

			if(matrix[i][j]==0){
				matrix[i][j] == 999;
			}

		}
	}
	*/

	//pasirenkam source virsune
	std::cout << "Starting node" << std::endl;
	int src;
	std::cin >> src;

	dijakstra(src, 6, matrix);


}

void print(int d[], int totalV, int src) {
	std::cout << std::endl;
	std::cout << "Distance from " << src << " to other nodes " << std::endl;
	
	for (int i = 0; i < 6; i++) {

		std::cout << i << " - " << d[i];
		std::cout << std::endl;
	}
	
}

void dijakstra(int src, int totalV, int matrix[][6]) {

	int distance[6];
	bool visited[6];

	int min;

	int nextNode = 0;

	for (int i = 0; i < 6; i++) {
		visited[i] = false;
	}

	for (int i = 0; i < 6; i++) 
		distance[i] = matrix[src][i];


	distance[src] = 0;
	visited[src] = true;
	
	for (int i = 0; i < 6; i++) {

		min = INT_MAX;
		
		for (int j = 0; j < 6; j++) {
			
			if (min > distance[j] && !visited[j]) {

				min = distance[j];
				nextNode = j;
			}
		}

		visited[nextNode] = true;

		for (int i = 0; i < 6; i++) {

			if (!visited[i]) {

				if (min + matrix[nextNode][i] < distance[i]) {
					distance[i] = min + matrix[nextNode][i];

				}
			}
		}
	}

	print(distance, 6, src);
}


This part I can't understand.

I know that the first for block finds the min value. But how?

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
 
for (int i = 0; i < 6; i++) {

		min = INT_MAX;
		
		for (int j = 0; j < 6; j++) {
			
			if (min > distance[j] && !visited[j]) {

				min = distance[j];
				nextNode = j;
			}
		}

		visited[nextNode] = true;

		for (int i = 0; i < 6; i++) {

			if (!visited[i]) {

				if (min + matrix[nextNode][i] < distance[i]) {
					distance[i] = min + matrix[nextNode][i];

				}
			}
		}
	}
Last edited on
jonnin (11331)
Its gonna be hard to understand this algorithm if a find-min is giving you troubles :P

say you have 3 nodes to look at, distances of 10,5, and 12.
min = 10000000000000000000000;
if min > 10 (first thing in distance)
min = distance. ok, now min is 10.
do irrelevant stuff.
loop #2 is 10 > 5 yes, it is.
min = 5;
do stuff..
loop 3 is 5 > 12? nope, skip.
min is 5. success.

distance happens to be a moving target due to the second block, but as far as the logic is concerned it may as well be a predetermined list.
Last edited on
Peter87 (11175)
If you want to understand an algorithm it's usually easier to read some higher-level description (e.g. pseudocode, or just plain text) than looking at an implementation. After you have understood how the algorithm works you will hopefully be able to understand the implementation easier.

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Description
Last edited on
Topic archived. No new replies allowed.