C++

Forum

 
Dijkstra Algorithm won't terminate

henk13 (5)
Hi,

I've resumed a dijkstra school work from a few months ago and found that in special cases the main dijkstra while-loop won't terminate.I use a 2-dimensional int matrix for distances and when I've arrived at the end point I use the previous-array to get the backwardspath from end -> start.
Here is the 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
 
void Graph::dijkstra(int start, int end)
{
	int currentNode = start,	
		smallestCost = INFINITY;	
	int smallestCostIx = -1,
		infinity = INFINITY;
	bool allSearched = true;	

	bool *searched = new bool[this->nrOfAirports];	
	int *distance = new int[this->nrOfAirports];	
	int *previous = new int[this->nrOfAirports];	

	for(int ix = 0 ; ix < this->nrOfAirports ; ix++)	
	{
		searched[ix] = false;
		distance[ix] = INFINITY;
		previous[ix] = -1;	
	}
	distance[start] = 0;	//A -> A = 0
	searched[start] = true;
	for(int ix = 0 ; ix < this->nrOfAirports; ix++)
	{
		if(!searched[ix])
		{
			allSearched = false;
		}
	}

	while(!searched[end] && !allSearched)	
	{
		smallestCost = INFINITY;
		for(int ix = 0 ; ix < this->nrOfAirports; ix++)
		{
			if(this->matrix[currentNode][ix] > 0 && !searched[ix])	
			{
				if(distance[ix] == infinity)	
				{
					distance[ix] = distance[currentNode] + this->matrix[currentNode][ix];
				}
				if(distance[ix] < smallestCost)	
				{
					smallestCost = distance[ix];
					smallestCostIx = ix;
				}
			}
		}
		for(int ix = 0 ; ix < this->nrOfAirports; ix++)
		{
			if(this->matrix[smallestCostIx][ix] > 0)
			{
				if(distance[ix] > distance[smallestCostIx] + this->matrix[smallestCostIx][ix])
				{
					distance[ix] = distance[smallestCostIx] + this->matrix[smallestCostIx][ix];
					previous[ix] = smallestCostIx;
				}
			}
		}

		searched[smallestCostIx] = true;	
		currentNode = smallestCostIx;	
		allSearched = true;
		for(int ix = 0 ; ix < this->nrOfAirports; ix++)
		{
			if(!searched[ix])
			{
				allSearched = false;
			}	
		}
	}

	
	delete[]searched;
	delete[]distance;
	delete[]previous;
}

Why will it sometimes not terminate?
TheIdeasMan (6782)
Hi henk13


I suppose the thing to do is use the debugger to track variables.

Hope this helps
henk13 (5)
Thx for the reply.
I solved it in java later on.
smallestCostIx was supposed to be currentNode and the dijkstra algorithm was not followed 100%.
Topic archived. No new replies allowed.