C++

Forum

 
(C++) Djikstra's algorithm not getting the correct nodes

lynzoid (8)
I'm currently doing a Djikstra's algorithm and im really stuck! It finds the shortest path from a startnode to a endnode. I'm not getting the correct working out as it finds the correct first node but then branches off. In the output, the first part is the map holding the edges for djikstra's and the second part is which intersections it's using. If someone could tell me how i'm supposed to access the final path that would be great, at the moment I thought it was my last cout statement.

Why am I not getting the correct nodes?

Thanks for any help !

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
 
void dji(double map[50][50], int startNode,int endNode,int maxNodes)
{
    int Intersections[maxNodes], minNode = startNode, path[maxNodes], curNode;
    double Distances[maxNodes], minValue = 999999;

    for(int a = 0; a < maxNodes; a++)
    {
        Intersections[a] = a+1;
        Distances[a] = map[startNode-1][a];
        path[a] = startNode;
    }
    Intersections[startNode-1] = -1;
    Distances[startNode-1] = 0;

    while(Intersections[endNode-1] != -1)
    {
        for (int i = 0; i < maxNodes; i++) 
        {
            if(Distances[i] > 0 && Distances[i] < minValue && Intersections[i] != -1)
            {
                minValue = Distances[i];
                minNode = i;
            }
        }
        minValue = 999999;

        Intersections[minNode] = -1;
        cout << "Used - " << minNode+1 << endl; 

        for(int i = 0; i < maxNodes; i++)
        {
            cout << Intersections[i] << " ";

        }

        for(int i = 0; i < maxNodes; i++)
        {
            if(Distances[i] > Distances[minNode] + map[minNode][i]) //&& Intersections[i] != -1)
            {
                Distances[i] = Distances[minNode] + map[minNode][i];
                path[i] = minNode;
            }
        }
    }
    cout << path[startNode] << " " << path[path[startNode]] << " " << path[path[path[startNode]]];
}


It goes from 19 -> 1 - > 4 which isn't possible from 1 -> 4

Output is:

http://imgur.com/MAImJmI
Last edited on
lynzoid (8)
Could somebody help me with this? I'm really stuck and can't progress
ne555 (10692)
> imgur
your problem is not graphic related, don't post an image.
$ ./a.out > output
would redirect the output to a file


> It goes from 19 -> 1 - > 4
I cannot see your path reconstruction.
¿or are you referring that it prints `Used - 1' and then `Used - 4'?



> cout << path[startNode]
¿shouldn't that be path[ startNode-1 ]?
but in `path' you save the previous node, there is no previous to the start ¿?


Please provide enough code to reproduce your problem.
lynzoid (8)
I'm programming Djikstra's algorithm in C++ and I'm getting the correct distances from the source node to the end node but i'm having trouble backtracking the previous nodes visited. It's giving me sort of the correct answer but not the correct answer. Also I noticed with different input data of 1 as the start node and 16 as the finish node that my algorithm is using path's that aren't allowed (it goes from 1 -> 10 -> 8 when 8 isn't allowed) but that could just be me getting path backtracking wrong.

http://pastebin.ca/3188762 - Input data (1st = max nodes and then nodes(node num, x,y) then max edges then all edges with the last line being the start and finish node)

http://textuploader.com/awp89 - Output in console

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
 
    #include<iostream>
    #include<fstream>
    
    using namespace std;
    
    struct Node
    {
    	int nodeNum;
    	double x, y;
    };

    void dji(double map[50][50],int startNode,int endNode,int maxNodes);
    
    int main()
    {
    	int tempA, tempB, maxNodes, maxEdges, startNode, endNode;
    	double tempD;
    	double map[50][50];
    	
    	ifstream fin;
    	fin.open("ass03.txt");
    	if(fin.good())
    	{
    		fin >> maxNodes;
    		
    		Node allNodes[maxNodes];
    		for(int i = 0; i < maxNodes; i++)
    		{
    			for(int k = 0; k < maxNodes; k++)
    			{
    				map[i][k] = -1;
    			}
    			map[i][i] = 0;
    		}
    
    		for(int i = 0; i < maxNodes; i++)
    		{
    			fin >> allNodes[i].nodeNum >> allNodes[i].x >> allNodes[i].y;
    		}
    		fin >> maxEdges;
    		
    		for(int i = 0; i < maxEdges; i++)
    		{
    			fin >> tempA >> tempB >> tempD;
    			map[tempA-1][tempB-1] = tempD;
    			map[tempB-1][tempA-1] = tempD;
    		}
    	
    		fin >> startNode >> endNode;
    		
    		
    		cout << "\t";
    		
    		for(int i = 0; i < maxNodes; i++)
    		{
    			cout << i+1 << "\t";
    		}
    		cout << endl;
    		for(int i = 0; i < maxNodes; i++)
    		{
    			cout << i+1 << "\t";
    			for(int k = 0; k < maxNodes; k++)
    			{
    				cout << map[i][k] << "\t";
    			}
    			cout << endl;
    		}
    		
    		
    		dji(map, startNode, endNode, maxNodes);
    		
    	}
    	else
    	{
    		cout << "Incorrect filename" << endl;
    	}
    
    
    	return 0;
    }
    
    
   

     void dji(double map[50][50], int startNode,int endNode,int maxNodes)
    {
    	int Intersections[maxNodes], path[maxNodes], temp; // equate for actual endNode
    	double Distances[maxNodes];
    	
    	for(int a = 0; a < maxNodes; a++)
    	{
    		Intersections[a] = a;
    		Distances[a] = map[startNode][a];
    		
    		if(map[startNode][a] != -1)
    		{
    			path[a] = startNode;
    		}
    		else
    		{
    			path[a] = -1;
    		}
    	}
    	Intersections[startNode] = -1;
    	Distances[startNode] = 0;
    	
    	double minValue = 99999;
    	int minNode = 0;
    
    	for(int l = 0; l < maxNodes; l++)//loop max amount of times to avoid having to function loop (disconsider l = startNode)?
    	{
    		for (int i = 0; i < maxNodes; i++)
    		{
    		    	if(Intersections[i] == -1)
    		    	{
    		    		continue;
    		    	}
    			
    		    	if(Distances[i] > 0 && Distances[i] < minValue)
    		    	{
    				minValue = Distances[i];
    				minNode = i;
    		    	}
    		}
    		
    		
    		if(Intersections[minNode] == endNode)
    		{
    			temp = l;
    		}
    		
    		Intersections[minNode] = -1;
    		
    		cout << " --- Used Node - " << minNode+1 << endl;
    		
    		for(int i = 0; i < maxNodes; i++)
    		{
    			cout << Intersections[i] << " ";
    		
    		}
    		cout << endl;
    
    		for(int i = 0; i < maxNodes; i++) 
    		{
    			if(map[minNode][i] < 0)
    			{
    				continue;
    			}
    
    		 	if(Distances[i] < 0) 
    			{
    				Distances[i] = minValue + map[minNode][i];
    				path[i] = minNode;
    				continue;
    			}
    			    
    			if((Distances[minNode] + map[minNode][i]) < Distances[i]) 
    			{
    				Distances[i] = minValue + map[minNode][i];
    				path[i] = minNode;
    			}
    		}
    		
    		minValue = 99999;
    	}
    	
    	for(int i = 0; i < maxNodes; i++)
    	{
    		cout << "Node:"  << i+1 << " - PATH= " << path[i] << "     distance = " << Distances[i]  << endl;
    	}
    	
    	cout << "Additional nodes used: " << temp << endl;
    	
    	temp = path[endNode];
    	for(int i = 0; i < 4; i++)
    	{
    		cout << temp << " ";
    		temp = path[temp];
    	}
    	
    	/*temp = path[endNode];
    	
    	int temp2 = path[endNode];
    	
    	for(int i = 0; i < maxNodes; i++)
    	{
    		if(i == 0)
    		{
    			cout << endNode << " ";
    			cout << temp << " ";
    		}
    		if(i%2 == 0)
    		{
    			if(temp != endNode)
    			{
    				temp = path[temp2];
    				cout << temp << " ";
    			}
    			else
    			{
    				cout << temp << " ";
    				i = maxNodes;
    			}
    		}
    		else
    		{
    			if(temp2 != endNode)
    			{
    				temp2 = path[temp]-1;
    				cout << temp2 << " ";
    			}
    			else
    			{
    				cout << temp2 << " ";
    				i = maxNodes;
    			}
    		}
    	}*/
    
    	//cout << "PATH = " << endNode << " < - " << path[endNode] << " < - " << path[path[endNode]-1] << " < - " << path[path[path[endNode]-1]-1] <<  endl;
    	
    	//cout << "TEST" << path[4] << " " << path[8] << " " << path[16] << " " << endl;
    }



Thank you for any help
Also I can't use STL.
Last edited on
ne555 (10692)
1
2
3
4
5
6
 
    			fin >> tempA >> tempB >> tempD;
    			map[tempA-1][tempB-1] = tempD;
//...
dji(map, startNode, endNode, maxNodes);
    	Intersections[startNode] = -1;
    	Distances[startNode] = 0;
¿what's your convention?
Nodes go from 1 to N and are stored on position 0 to N-1, but then you refer `startNode' directly instead of `startNode-1'
lynzoid (8)
What would you change to get a working dijkstra's algorithm? Cause even when I change it to work for the startNode - 1 it doesn't work for me
Last edited on
lynzoid (8)
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
 
void dji(double map[50][50], int startNode,int endNode,int maxNodes)
{
	int Intersections[maxNodes], path[maxNodes], temp; // equate for actual endNode
	double Distances[maxNodes];
	
	for(int a = 0; a < maxNodes; a++)
	{
		Intersections[a] = a;
		Distances[a] = map[startNode][a];
		
		if(map[startNode][a] > 0)
		{
			path[a] = startNode;
		}
		else
		{
			path[a] = -1;
		}
	}
	Intersections[startNode] = -1;
	Distances[startNode] = 0;
	
	double minValue = 99999;
	int minNode = 0;


	for(int l = 0; l < maxNodes; l++)//loop max amount of times to avoid having to function loop (disconsider l = startNode)?
	{
		for (int i = 0; i < maxNodes; i++)
		{
		    	if(Intersections[i] == -1)
		    	{
		    		continue;
		    	}
			
		    	if(Distances[i] > 0 && Distances[i] < minValue)
		    	{
				minValue = Distances[i];
				minNode = i;
		    	}
		}
		
		
		if(Intersections[minNode] == endNode)
		{
			temp = l;
		}
		
		Intersections[minNode] = -1;
		
		cout << " --- Used Node - " << minNode+1 << endl;
		
		for(int i = 0; i < maxNodes; i++)
		{
			cout << Intersections[i] << " ";
		
		}
		cout << endl;

		for(int i = 0; i < maxNodes; i++) 
		{
			if(map[minNode][i] < 0)
			{
				continue;
			}

		 	if(Distances[i] < 0) 
			{
				Distances[i] = minValue + map[minNode][i];
				path[i] = minNode;
				continue;
			}
			    
			if((Distances[minNode] + map[minNode][i]) < Distances[i]) 
			{
				Distances[i] = minValue + map[minNode][i];
				path[i] = minNode;
				
			}
		}
		
		minValue = 99999;
	}
	
	for(int i = 0; i < maxNodes; i++)
	{
		cout << "Node:"  << i+1 << " - PATH= " << path[i] << "     distance = " << Distances[i]  << endl;
	}
	cout << "Additional nodes used: " << temp << endl;
	
	temp = path[endNode];
	for(int i = 0; i < 4; i++)
	{
		cout << "temp: "<< i << " - " << temp+1 << endl;
		temp = path[temp];
	}
}


This works for 19 to 16 but if I try an instance of 2 to 8 it doesn't work and I don't get it!

P.S : The startNode and endNode being passed in are now index's as I minused 1 off them
Last edited on
ne555 (10692)
¿what do you mean by "it doesn't work"?
¿doesn't give you the minimal path, it gives you a non-existant path, crash?


This is for 2 8
Node:1 - PATH= 2     distance = 3.5
Node:2 - PATH= 0     distance = 0
Node:3 - PATH= 13     distance = 5.8
Node:4 - PATH= 19     distance = 8.3
Node:5 - PATH= 7     distance = 10.3
Node:6 - PATH= 7     distance = 10.9
Node:7 - PATH= 3     distance = 7.3
Node:8 - PATH= 4     distance = 10.7
Node:9 - PATH= 10     distance = 8.9
Node:10 - PATH= 1     distance = 5.9
Node:11 - PATH= 1     distance = 6.3
Node:12 - PATH= 2     distance = 2.7
Node:13 - PATH= 2     distance = 3.9
Node:14 - PATH= 13     distance = 8.9
Node:15 - PATH= 6     distance = 14.3
Node:16 - PATH= 5     distance = 12.7
Node:17 - PATH= 18     distance = 10.3
Node:18 - PATH= 10     distance = 7.6
Node:19 - PATH= 1     distance = 5.9
Node:20 - PATH= 7     distance = 9.1
Additional nodes used: 15
temp: 0 - 4
temp: 1 - 19
temp: 2 - 1
temp: 3 - 2
which is a valid path (but haven't checked if minimal)

calling as dji(map, startNode-1, endNode-1, maxNodes);
and changing the output to cout << "Node:" << i+1 << " - PATH= " << path[i]+1 << " distance = " << Distances[i] << endl;
(the index is stored, the name is one more)
lynzoid (8)
I guess that makes sense but try 2 to 20, it won't work correctly and I don't understand why
lynzoid (8)
Actually, it might be working and i'm just stupid.
Topic archived. No new replies allowed.