A *アルゴリズムでメモリが不足している

Question

私はDijkstraの方法をノードを通過させるために使用しています。小さな入力でも問題なく動作します。

しかし、非常に大きな入力（5000個の頂点と500万の辺のグラフのような）があると、検出された頂点を優先順位キューにプッシュする行にstd :: bad_allocエラーが発生します。

どうすればこの問題を解決できますか？

int distance; 
    priority_queue<detectedVertex, vector<detectedVertex>, Compare> detectedVertices; 
    detectedVertex s(source, graph[source].strLineDist); 
    detectedVertices.push(s); 

    while (!detectedVertices.empty()) { 
     int ID=detectedVertices.top().ID; 
     int cost=detectedVertices.top().estimatedCost-graph[ID].strLineDist; 
     if(ID==destination) { 
      distance=cost; 
      break; 
     } 
     detectedVertices.pop(); 
     graph[ID].visited=true; 

     for(int i=0;i<graph[ID].adjList.size();i++) { 
      int adjID=graph[ID].adjList[i].v2; 
      int edgeWeight=graph[ID].adjList[i].weight; 
      if(!graph[adjID].visited) { 
       detectedVertex temp(adjID, cost+edgeWeight+graph[adjID].strLineDist); 
       detectedVertices.push(temp); //std::bad_alloc 
      } 
     } 
    } 

誰が

struct Edge { 
    int v1; 
    int v2; 
    int weight; 

    Edge(int v1, int v2, int weight) { 
     this->v1 = v1; 
     this->v2 = v2; 
     this->weight = weight; 
    } 
}; 

struct Vertex { 
    int ID = 0; 
    vector<Edge> adjList; 
    bool visited = false; 
    int strLineDist = 0; 
}; 

struct detectedVertex { 
    int ID; 
    int estimatedCost; 

    detectedVertex(int ID, int estimatedCost) { 
     this->ID = ID; 
     this->estimatedCost = estimatedCost; 
    } 
}; 

Answer 1

問題はここにある不思議場合、私の構造体：

detectedVertex temp(adjID, cost+edgeWeight+graph[adjID].strLineDist);

detectedVertices.push(temp); //std::bad_alloc

を210

あなたはキュー内の頂点を何度も押していますが、これはダイクストラでは起こりません。 adjIDノードがすでに更新されていても（まだ訪問されていない場合）、ノードはすでにキューに入っています。その後、別の "先行者"が来て、それをもう一度更新します。キューは、特にこのような大きなグラフの場合には、爆発的に使用されます。

これはメモリが爆発する問題を解決するためのものです。一方、私はこのダイクストラの実装は私にとって間違っていると言わざるを得ない。あなたはそれを改訂する必要があります、IMHO。