如何加快dijkstra單一來源，單向目標與回溯？

我試圖解決迪傑斯特拉問題Alpha #20 Prob C，並且正在獲取案例31的TLE，它具有100000節點和99999邊緣。我假設我的代碼的複雜性爲O（E lg V），大約爲499995。我認爲速度足夠快，但由於結果不成功，我使用內聯代碼進行回溯，並在目標節點從隊列中刪除後立即進行一些優化，比如突破dijkstra。我不認爲這會影響結果，就像一個節點被刪除一樣，這意味着找到了最佳路徑，我們可以享受。我現在已經用盡了優化這些代碼的想法，因此已經到了這裏。代碼如下：如何加快dijkstra單一來源，單向目標與回溯？

#include <iostream> 
#include <vector> 
#include <set> 
#include <cstdio> 
#include <climits> 
#include <limits> 
using namespace std; 

typedef pair<int, int> ii; 
typedef vector<ii> vii; 
typedef vector<int> vi; 
typedef vector<vii> vvii; 

vi D; 
vi parent; 
vi path; 
vvii graph; 


void dijkstra(int i, int j) 
{ 
     set<ii> Q; 
     Q.insert(ii(0, i)); 
     D[i] = 0; parent[i] = -555; 
     bool checked = false; 
     while(!Q.empty()) 
     { 
       ii top = *Q.begin(); 
      Q.erase(Q.begin()); 
      int topnode = top.second; 
      for(vii::iterator it = graph[topnode].begin();it != graph[topnode].end();it++) 
      { 
       int v = it->first, d2 = it->second; 
       if(D[v] > D[topnode] + d2) 
        { 
         if(D[v] != INT_MAX) 
         { 
           Q.erase(Q.find(ii(D[v], v))); 
         } 
         D[v] = D[topnode] + d2; parent[v] = topnode; 
         Q.insert(ii(D[v], v)); 
         if(v == j) 
           checked = true; 
        } 
      } 
      if(checked) 
      { 
       if(Q.find(ii(D[j], j)) == Q.end()) 
        break; 
      } 
     } 
} 

/* void backtrack(int n) 
{ 
    if(parent[n] != -555) 
    { 
     path.push_back(n); 
     backtrack(parent[n]); 
    } 
} 

void backtrack2(int n) 
{ 
    while(parent[n] != -555) 
    { 
     path.push_back(n); 
     n = parent[n]; 
    } 
} */ 

int main(void) { 
    int n, m, x, y, z; 
    scanf("%d%d", &n, &m); 
    graph.clear(); graph.resize(n); D.resize(n, INT_MAX); parent.resize(n, -1); 
    while(m--) 
    { 
     scanf("%d%d%d", &x, &y, &z); 
     graph[x-1].push_back(ii(y-1, z)); 
     graph[y-1].push_back(ii(x-1, z)); 
    } 
    dijkstra(0, n-1); 
    if(D[n-1] == INT_MAX) 
     printf("-1\n"); 
    else 
    { 
     int x = n-1; 
     while(parent[x] != -555) 
     { 
      path.push_back(x); 
      x = parent[x]; 
     } 
     printf("1 "); 
     for(int i = int(path.size())-1;i >= 0;i--) 
     { 
      printf("%d ", path[i]+1); 
     } 
     printf("\n"); 
    } 
}

我不知道我能做些什麼來提高速度。我已經嘗試減少遞歸調用開銷和更多的可能。如果任何人有任何其他的想法，或者可以指出某種錯誤（如果有的話）（優化），會高度讚賞。現在我認爲可以做的唯一事情就是使用priority_queue（而不是set），但我認爲這不會影響性能。

謝謝！

筆尖

來源

2015-02-10 Nalin Bhardwaj

看看這個，dijkstra使用優先級隊列https://ronzii.wordpress.com/2011/07/07/dijkstras-algorithm-using-stl/ – g4ur4v 2015-02-10 05:48:49

@ g4ur4v真的非常感謝，我知道使用優先級隊列速度，但我剛剛檢查了[STL的Topcoder教程]（http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2），它說在dijkstra中使用'set'而不是'priority_queue' 〜0.1％的差異，我嚴重懷疑可以幫助在這種情況下。另外，我已經在最後一段中提到過自己的優化... – 2015-02-10 05:52:57

一種可能的加速是在圖形創建時合併相同頂點之間的多條邊。 – 2015-02-10 07:17:43

你的解決方案似乎主要是細到我，O(E log V)這個約束是綽綽有餘。

您的問題很可能是由於您使用整數，特別是您使用INT_MAX作爲比任何可能的路徑長度更長的事實。隨着10^5邊緣和權重高達一百萬int是不夠的。只要你溢出並得到負權重，所有的迪克斯特拉不變量都會中斷，甚至不能保證終止。

與long long小號替換所有的int s和INT_MAX的東西比10^11大，而且您的解決方案將最有可能通過。

來源

2015-02-10 07:12:34 Ishamael

如何加快dijkstra單一來源，單向目標與回溯？

回答

相關問題