c++ - Dijkstra's algorithm - adjacency matrix and list -

i've got strange problem dijkstra's implementation... have 2 algorithms, 1 adjacency matrix , second 1 adjacency list. identical , difference passing numbers these structures.

i keep numbers matrix in simple two-dimensional matrix called weightmat. numbers list kept in array of lists called nbhlist. lists composed structs called listnode.

struct listnode{             int number;                      int weight;                  listnode* next;                      listnode(){                                      number = weight = 0;             next = 0;         }     }; 

and few general variables: vertex (number of vertices), edge (number of edges), vstart (number of start vertex).

now code of dijkstra's algorithm matrix:

typedef vector<vector<pair<int, float> > > graph; struct compare{     int operator() (const pair<int,float>& p1, const pair<int,float>& p2)     {         return p1.second > p2.second;     } };  vector<float> d(vertex); vector<int> parent(vertex);  (int = 0; < vertex; i++){     d[i] = numeric_limits<float>::max();     parent[i] = -1; }  priority_queue<pair<int, float>, vector<pair<int, float> >, compare> matqueue;  d[vstart] = 0; matqueue.push(make_pair(vstart, d[vstart])); while (!matqueue.empty()){     int u = matqueue.top().first;     if (u == vertex - 1) break;     matqueue.pop();     (int = 0; < vertex; i++){         if (weightmat[u][i] != 0){             int v = i;             float w = weightmat[u][i];             //cout << "u " << u << "number " << << " weight " << weightmat[u][i] << endl;             if (d[v]> d[u] + w){                 d[v] = d[u] + w;                 parent[v] = u;                 matqueue.push(make_pair(v, d[v]));             }         }     } }  vector<int> path; path.clear(); int p = vertex - 1; path.push_back(vertex - 1); while (p != vstart) {     p = parent[p];     path.push_back(p); } (int = path.size()-1; >=0; i--){     cout << path[i] << "->"; } 

and code of dijkstra's algorithm lists:

typedef vector<vector<pair<int, float> > > graph;      struct compare{         int operator() (const pair<int, float>& p1, const pair<int, float>& p2)         {             return p1.second > p2.second;         }     };      vector<float> d(vertex);     vector<int> parent(vertex);      (int = 0; < vertex; i++){         d[i] = numeric_limits<float>::max();         parent[i] = -1;     }      priority_queue<pair<int, float>, vector<pair<int, float> >, compare> matqueue;      d[vstart] = 0;     matqueue.push(make_pair(vstart, d[vstart]));      listnode* hand = new listnode;      while (!matqueue.empty()){         int u = matqueue.top().first;         if (u == vertex - 1) break;         matqueue.pop();         hand = nbhlist[u];         while (hand){             int v = hand->number;             float w = hand->weight;             //cout << "u " << u << "number " << v << " weight " << w << endl;             hand = hand->next;             if (d[v] > d[u] + w){                 d[v] = d[u] + w;                 parent[v] = u;                 matqueue.push(make_pair(v, d[v]));             }         }     }       vector<int> path;     path.clear();     int p = (vertex-1);     path.push_back(p);     while (p != vstart)     {         p = parent[p];         path.push_back(p);     }     cout << endl << endl;     (int = path.size() - 1; >= 0; i--){         cout << path[i] << "->";     } 

as said, identical. difference:

matqueue.pop();         hand = nbhlist[u];         while (hand){             int v = hand->number;             float w = hand->weight;             //cout << "u " << u << "number " << v << " weight " << w << endl;             hand = hand->next;             if (d[v] > d[u] + w){                 d[v] = d[u] + w;                 parent[v] = u;                 matqueue.push(make_pair(v, d[v]));             }         } 

and:

matqueue.pop();         (int = 0; < vertex; i++){             if (weightmat[u][i] != 0){                 int v = i;                 float w = weightmat[u][i];                 //cout << "u " << u << "number " << << " weight " << weightmat[u][i] << endl;                 if (d[v]> d[u] + w){                     d[v] = d[u] + w;                     parent[v] = u;                     matqueue.push(make_pair(v, d[v]));                 }             }         } 

my problem - give me different outputs , have no idea why. me find problem?

one possible bug in listnode struct:

struct listnode{             int number;                      int weight;                  listnode* next;                      listnode(){                                      number = weight = 0;             next = 0;         }     }; 

weight int, weights floats according rest of code, might result in unwanted truncation.