Dijkstra std :: priority_queue的最短路徑算法性能vs std :: set

Question

我想了解這些容器在時間複雜度方面的主要區別。 我嘗試Dijkstra算法的3個實施方式中，如下所述：與用作隊列

2-與STL priority_queue

3-與STL一個簡單的數組

1-設置

的我測試過的圖很大，它包含超過150000個頂點，並且所有邊的權重都是正的。

我得到的結果如下：

1 - 與陣列算法是很慢 - >預計

2 - 用STL priority_queue算法跑了很多比陣列快 - - >這也是預期的

3 - 使用STL設置算法運行速度非常快，我說的是比priority_queue快100倍 - >我沒想到會看到這個巨大的性能...

知道std :: priority_queue和std :: set是存儲元素的數據容器，兩者基本上具有相同的插入複雜度O（log n），我不明白它們之間的性能差異。你有什麼解釋嗎？

感謝您的幫助，

編輯： 這裏是我實現的一個抽象：

用的std ::設置：

unsigned int Graphe::dijkstra(size_t p_source, size_t p_destination) const { 

.... 


set<pair<int, size_t>> set_vertices; 


vector<unsigned int> distance(listAdj.size(), 
     numeric_limits<unsigned int>::max()); 


vector < size_t 
     > predecessor(listAdj.size(), 
       numeric_limits <size_t> ::max()); 


distance[p_source] = 0; 
set_vertices.insert({ 0, p_source }); 


while (!set_vertices.empty()) { 

    unsigned int u = set_vertices.begin()->second; 


    if (u == p_destination) { 
     break; 
    } 

    set_vertices.erase({ distance[u], 
      u }); 


    for (auto itr = listAdj[u].begin(); 
      itr != listAdj[u].end(); ++itr) { 


     int v = itr->destination; 
     int weigth = itr->weigth; 


     if (distance[v] 
       > distance[u] + weigth) { 


      if (distance[v] 
        != numeric_limits<unsigned int>::max()) { 
       set_vertices.erase(
         set_vertices.find(
           make_pair(distance[v], 
             v))); 
      } 

      distance[v] = distance[u] + weigth; 

      set_vertices.insert({ distance[v], 
        v }); 

      predecessor[v] = u; 
     } 
    } 
} 

.... 

return distance[p_destination];} 

與priority_queue：

unsigned int Graphe::dijkstra(size_t p_source, size_t p_destination) const { 

... 

typedef pair<size_t, int> newpair; 

priority_queue<newpair, vector<newpair>, greater<newpair> > PQ; 

vector<unsigned int> distance(listAdj.size(), 
     numeric_limits<unsigned int>::max()); 


vector < size_t 
     > predecessor(listAdj.size(), 
       numeric_limits <size_t> ::max()); 


distance[p_source] = 0; 
PQ.push(make_pair(p_source, 0)); 

while (!PQ.empty()) { 


    unsigned int u = PQ.top().first; 


    if (u == p_destination) { 
     break; 
    } 

    PQ.pop(); 


    for (auto itr = listAdj[u].begin(); 
      itr != listAdj[u].end(); ++itr) { 


     int v = itr->destination; 
     int weigth = itr->weigth; 


     if (distance[v] 
       > distance[u] + weigth) { 

      distance[v] = distance[u] + weigth; 

      PQ.push(
        make_pair(v, distance[v])); 

      predecessor[v] = u; 
     } 
    } 
} 
... 

return distance[p_destination];} 

Answer 1

std::priority_queue的基礎數據結構是一個最大堆，它的自我平衡二分搜索 - 基本上是C++的紅黑樹。因此它們都確保了插入，刪除和更新操作的時間複雜度爲O(logn)。

但是，正如我所提到的，std::set的平衡二叉搜索樹正在被自動平衡以保持其高度對數節點的高度對數，這確保了對數查詢的複雜性，而與插入順序或任何操作無關。 std::priority_queue不是自我平衡的，並且可以根據插入順序非常平坦。雖然自我平衡有它自己的成本，所以在去除頂部之後進行堆積，但我認爲這是性能提高的原因。

希望它有幫助！