(C++) Dijkstra's Algorithm Backtracking issues -

i'm programming djikstra's algorithm in c++ , i'm getting correct distances source node end node i'm having trouble backtracking previous nodes visited. it's giving me sort of correct answer not correct answer. noticed different input data of 1 start node , 16 finish node algorithm using path's aren't allowed (it goes 1 -> 10 -> 8 when 8 isn't allowed) me getting path backtracking wrong.

http://pastebin.ca/3188762 - input data (1st = max nodes , nodes(node num, x,y) max edges edges last line being start , finish node)

http://textuploader.com/awp89 - output in console

code:

#include<iostream> #include<fstream>  using namespace std;  struct node {     int nodenum;     double x, y; };  void dji(double map[50][50],int startnode,int endnode,int maxnodes);  int main() {     int tempa, tempb, maxnodes, maxedges, startnode, endnode;     double tempd;     double map[50][50];      ifstream fin;     fin.open("ass03.txt");     if(fin.good())     {         fin >> maxnodes;          node allnodes[maxnodes];         for(int = 0; < maxnodes; i++)         {             for(int k = 0; k < maxnodes; k++)             {                 map[i][k] = -1;             }             map[i][i] = 0;         }          for(int = 0; < maxnodes; i++)         {             fin >> allnodes[i].nodenum >> allnodes[i].x >> allnodes[i].y;         }         fin >> maxedges;          for(int = 0; < maxedges; i++)         {             fin >> tempa >> tempb >> tempd;             map[tempa-1][tempb-1] = tempd;             map[tempb-1][tempa-1] = tempd;         }          fin >> startnode >> endnode;           cout << "\t";          for(int = 0; < maxnodes; i++)         {             cout << i+1 << "\t";         }         cout << endl;         for(int = 0; < maxnodes; i++)         {             cout << i+1 << "\t";             for(int k = 0; k < maxnodes; k++)             {                 cout << map[i][k] << "\t";             }             cout << endl;         }           dji(map, startnode-1, endnode-1, maxnodes);      }     else     {         cout << "incorrect filename" << endl;     }       return 0; }      void dji(double map[50][50], int startnode,int endnode,int maxnodes) {     int intersections[maxnodes], path[maxnodes], temp; // equate actual endnode     double distances[maxnodes];      for(int = 0; < maxnodes; a++)     {         intersections[a] = a;         distances[a] = map[startnode][a];          if(map[startnode][a] != -1)         {             path[a] = startnode;         }         else         {             path[a] = -1;         }     }     intersections[startnode] = -1;     distances[startnode] = 0;      double minvalue = 99999;     int minnode = 0;      for(int l = 0; l < maxnodes; l++)//loop max amount of times avoid having function loop (disconsider l = startnode)?     {         (int = 0; < maxnodes; i++)         {                 if(intersections[i] == -1)                 {                     continue;                 }                  if(distances[i] > 0 && distances[i] < minvalue)                 {                 minvalue = distances[i];                 minnode = i;                 }         }           if(intersections[minnode] == endnode)         {             temp = l;         }          intersections[minnode] = -1;          cout << " --- used node - " << minnode+1 << endl;          for(int = 0; < maxnodes; i++)         {             cout << intersections[i] << " ";          }         cout << endl;          for(int = 0; < maxnodes; i++)          {             if(map[minnode][i] < 0)             {                 continue;             }              if(distances[i] < 0)              {                 distances[i] = minvalue + map[minnode][i];                 path[i] = minnode;                 continue;             }              if((distances[minnode] + map[minnode][i]) < distances[i])              {                 distances[i] = minvalue + map[minnode][i];                 path[i] = minnode;             }         }          minvalue = 99999;     }      for(int = 0; < maxnodes; i++)     {         cout << "node:"  << i+1 << " - path= " << path[i] << "     distance = " << distances[i]  << endl;     }      cout << "additional nodes used: " << temp << endl;      temp = path[endnode];     for(int = 0; < 4; i++)     {         cout << temp << " ";         temp = path[temp];     }      /*temp = path[endnode];      int temp2 = path[endnode];      for(int = 0; < maxnodes; i++)     {         if(i == 0)         {             cout << endnode << " ";             cout << temp << " ";         }         if(i%2 == 0)         {             if(temp != endnode)             {                 temp = path[temp2];                 cout << temp << " ";             }             else             {                 cout << temp << " ";                 = maxnodes;             }         }         else         {             if(temp2 != endnode)             {                 temp2 = path[temp]-1;                 cout << temp2 << " ";             }             else             {                 cout << temp2 << " ";                 = maxnodes;             }         }     }*/      //cout << "path = " << endnode << " < - " << path[endnode] << " < - " << path[path[endnode]-1] << " < - " << path[path[path[endnode]-1]-1] <<  endl;      //cout << "test" << path[4] << " " << path[8] << " " << path[16] << " " << endl; } 

thank help

the problem you're mixing zero-based , one-based indexing. vertices numbered 1-20, , numbers end in path array valid indices 0-19. use vertex number index array.

change code either consistently use vertex number, or consistently use array index.