-
Dijkstra's Algorithm?
Code:
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
Code:
void relax(vertex *a, vertex *b)
{
if(a->distance + weightFrom(a,b) > b->distance)
{
b->distance = a->distance + weightFrom(a,b);
b->pred = a;
}
}
-
output
this might be a problem as well.
when i did a deletemin, some of them are out of order.
output::
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
they are marked here. not sure what this means, sorry i'm a beginner at c++.