Алгоритм Дейкстры - матрица смежности и список

Question

У меня странная проблема с реализацией Dijkstra ... У меня есть 2 алгоритма: один для матрицы смежности и второй для списка смежности. Они почти идентичны, и только разница заключается в прохождении чисел из этих структур.

Я сохраняю числа из матрицы в простой двумерной матрице под названием weightmat. Номера из списка хранятся в массиве списков, называемых nbhlist. Списки состоят из структур, называемых ListNode.

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

И несколько общих переменных: вершинные (число вершин), краевые (число ребер), VSTART (количество начальной вершины).

Теперь код алгоритма Дейкстры для матрицы:

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); 

for (int i = 0; i < 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(); 
    for (int i = 0; i < vertex; i++){ 
     if (weightmat[u][i] != 0){ 
      int v = i; 
      float w = weightmat[u][i]; 
      //cout << "U " << u << "Number " << i << " 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); 
} 
for (int i = path.size()-1; i >=0; i--){ 
    cout << path[i] << "->"; 
} 

И это код алгоритма Дейкстры для моих списков:

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); 

    for (int i = 0; i < 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; 
    for (int i = path.size() - 1; i >= 0; i--){ 
     cout << path[i] << "->"; 
    } 

Как я уже говорил, они почти идентичны. Только разница:

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])); 
      } 
     } 

И:

MatQueue.pop(); 
     for (int i = 0; i < vertex; i++){ 
      if (weightmat[u][i] != 0){ 
       int v = i; 
       float w = weightmat[u][i]; 
       //cout << "U " << u << "Number " << i << " 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])); 
       } 
      } 
     } 

Моя проблема - они дают мне иногда разные выходы, и я понятия не имею, почему. Не могли бы вы помочь мне найти мою проблему?

Answer 1

Одна возможная ошибка в том, что в вашем ListNode структуры:

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

weight является int, но ваши веса float s в соответствии с остальной частью кода, который может привести к нежелательным усечения.