最有效的實現使用向量和對在C++ STL Dijkstra的最短路徑的

如果std::vector<vector<pair<int,int> > > v(n)代表與pair<int,int>圖的鄰接表是{vertex,weight}對，我試圖實現該算法通過以下方式：最有效的實現使用向量和對在C++ STL Dijkstra的最短路徑的

while (true) 
{ 
    long long yo = LLONG_MAX; 
    int ind = -1; 
    for (int i = 0; i < n; ++i) 
    { 
     if (ans[i] < yo && !v[i].empty()) 
     { 
      ind = i; 
      yo = ans[i]; 
     } 
    } 
    if (ind == -1) 
     break; 
    for (int i = 0; i < v[ind].size(); ++i) 
    { 
     if (ans[v[ind][i].first] > ans[ind] + v[ind][i].second) 
      ans[v[ind][i].first] = ans[ind] + v[ind][i].second; 
     v[ind].erase(v[ind].begin() + i); 
    } 
}

其中ans[i]存儲被初始化爲{LLONG_MAX,...0,...LLONG_MAX}，0爲源的最短路徑。由於這是我第一次嘗試實現它，是否有更好的方法來實現在stl中使用向量/列表（就時間/空間複雜性而言）？

來源

2017-04-11 yobro97

這個問題可能更適合[代碼評論]（http://codereview.stackexchange.com），因爲它似乎是關於已經工作的代碼。 – cdhowie

「更好」的條款是什麼？速度？內存使用情況？我個人認爲最可讀性;） – user463035818

@ tobi303時間和內存使用情況 – yobro97

當前的方法有邏輯錯誤（在迭代時修改矢量）。複雜性也很明顯，由於冗餘while循環每次獲得新的最小距離節點和不必要的擦除操作，這是由於整個鄰接列表的移位而造成的向量中的重載。

我建議使用優先級隊列< min heap>，它比Elog（N）更復雜，E是no。邊緣和N號。在圖中的節點。我只是複製粘貼我的舊代碼之一與評論。

#define P first 
#define Q second 
typedef long long LL ; 
typedef pair < LL , int > li ; 
typedef pair < int , LL > il ; 
dist[N] = {INT_MAX} ; // array containing the distance to each node from source node 
vector <il> adj [100010] ; // adjacency list with (node, distance) pair 

void dijkstra(int s){ // s is the source node 
    priority_queue < li , vector <li> , greater <li> > pq; // priortiy queue with a pair <long, int> as the data , using vector as underlying data structure and std:greater comparator 
    dist [s] = 0; 
    pq.push(li(dist[s], s)); 
    while(!pq.empty()){ 
     li u = pq.top() ; pq.pop() ; // u.P = current minimum distance of node , u.Q = current node on top of the heap 
     if(dist[u.Q] == u.P) 
     for(int i = 0 ; i < adj[u.Q].size() ; i++){ 
      il v = adj[u.Q][i] ; 
      if(dist[v.P] > u.P + v.Q){ 
       dist[v.P] = u.P + v.Q ; 
       pq.push(li(dis[v.P] ,v.P)); 
      } 
     } 
    }

如果您有任何問題，請隨時在評論中提問。

來源

2017-04-11 19:09:22

一些優化的Dijkstra：

使用堆。確保存儲頂點，而不是堆中的邊。
嘗試雙向方法。假設你必須找到一個從S到T的最短路徑。你可以同時運行2個Dijkstra：一個來自S，另一個來自T的反向邊緣。您可以使用某種啓發式方法在這2個Dijkstras之間切換。例如，與當前半徑最小的Dijkstra一起工作。

從理論上講，Dijkstra可以優化爲O（E + VlogV）與Fibonacci堆。但實際上它的運行速度較慢。

來源

2017-04-13 03:11:45 SashaMN

最有效的實現使用向量和對在C++ STL Dijkstra的最短路徑的

回答

相關問題