Dijkstra's Algorithm?

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
void Dijkstra(int s,int t)
	{
		vertex *verts = findVertex(grid[s][t]);
		Heap H;
		for each(vertex *v in vertexList)
		{
			
			if(v->data == verts->data)
			{
				verts->distance = 0;
				verts->pred = NULL;
			}
			v->distance = INFINITY;
			v->pred = NULL;
			H.insert(v->data);
		}
		while(H.size() != 0)
		{
			
			vertex *x = findVertex(H.deletemin());
		
			for each(edge *v in x->adjacencyList)
			{
				
				if(v->end->visited != true)
				{	
				relax(x,v->end);
				v->end->visited = true;
				}
				else
					break;
				
			}
			
		}
	}


is something missing in my dijkstra's, i keep getting an infinite loop. never implemented dijkstra's before so i'm kinda sketchy on how to do it.


my relax function

1
2
3
4
5
6
7
8
9
10
11
void relax(vertex *a, vertex *b)
	{
		
		if(a->distance + weightFrom(a,b) > b->distance)
			{
				b->distance = a->distance + weightFrom(a,b);
				b->pred = a;
			}
	

	}
bump

as well, my output when i do a looop on deletemin is out of order, any reason why this might be?

41
153
288
292
491
778
1842
1869
2995
3035
3902
4664
4827
5436
5447
5705
6334
6868
7711
8723
8942
9040
9741
9894
9961
11478
11538
11942
12316
12382
12859
14604
14771
15141
15724
17035
17421
17673
18467
19264
18716
19169
19718
19912
21726
22190
22648
23281
23811
24464
25667
20037
26299
26500
25547
16827
26962
27644
19895
28145
27529
28253
28703
29358
30106
30333
31322
32391
32662
32757
help?? :O
Topic archived. No new replies allowed.