Dijkstra's algorithm issue

Jakman217 (18)
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
ne555 (10692)
¿where do you visit your nodes?
Jakman217 (18)
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. );
Topic archived. No new replies allowed.