Dec 6, 2012 at 5:33am
After numerous Rewrites, and many different versions of this, I am stumped and frustrated.
It won't continue onto the next node in the sequence, it just stays at the start (0).
prevNode holds the weight, current node index, previous node index, and whether it's been visited or not.
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
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
|
prevNode* graph::search(int start, int **adjmat) // using dijkstra's algorithm
{
// setup
prevNode *ret;
ret = new prevNode[size];
// create node data
for( int i = 0; i < size; ++i)
{
ret[i].weight = 1.0/0.0;
ret[i].self = i;
ret[i].prev = -1;
ret[i].visited = false;
}
ret[start].weight = 0;
bool cont = true;
int u = 0;
// until set is empty, run
while(cont)
{
// pull out the closest unvisited node
for( int i = 0; i < size; ++i)
{
//std::cout << i << ' ' << u << std::endl;
if( ret[u].visited)
{
u = i;
//std::cout << "change in u" << std::endl;
}
else if( ret[u].weight > ret[i].weight)
{
u = i;
std::cout << "change in u" << std::endl;
}
}
// if the next closest to the begining is infinity break
if( ret[u].weight == 1.0/0.0)
return ret;
for( int v = 0; v < size; ++v)
{
if( adjmat[u][v] != 0)
{
double alt = ret[u].weight + adjmat[u][v];
//std::cout << alt << std::endl;
if( alt < ret[v].weight)
{
//std::cout << "change" << alt << ":" << ret[v].weight << std::endl;
ret[v].weight = alt;
ret[v].prev = u;
//std::cout << alt << ":" << ret[v].weight << std::endl;
}
}
}
// check for unvisited nodes
cont = false;
for( int i = 0; i < size; ++i)
{
if( !ret[i].visited)
cont = true;
}
}
return ret;
}
|
Last edited on Dec 6, 2012 at 5:35am
Dec 6, 2012 at 5:52am
¿where do you visit your nodes?
Dec 6, 2012 at 5:56am
I visit it when it is the node I'm connecting from, when it is u, and I just realized the problem. I feel stupid.
I never included the
ret[u].visited = true;
, huff.
Thank you. );
