Dijkstra的算法 - 鄰接矩陣和列表

Question

我的Dijkstra的實現有一個奇怪的問題...我有2個算法，一個用於鄰接矩陣，第二個用於鄰接列表。它們幾乎完全相同，只有通過這些結構傳遞的數字纔有所不同。

我將矩陣中的數字保存在稱爲weightmat的簡單二維矩陣中。 列表中的數字保存在名爲nbhlist的列表數組中。 列表由名爲ListNode的結構組成。

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

而且一些一般性的變量：頂點（頂點數量），邊（邊數），則vstart（起始頂點的數量）。 Dijkstra算法的

現在代碼矩陣：

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

這是我的名單Dijkstra算法的代碼：

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

和：

​​

我的問題是 - 他們給我有時不同的輸出，我不知道爲什麼。 你能幫我找到我的問題嗎？

Answer 1

一個可能的錯誤是，在你的ListNode結構：

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

weight是int，但你的權重是根據你的代碼的其餘部分，這可能會導致不必要的截斷float秒。