Выполнение алгоритма Дейкстры

Question

Ниже приведена реализация алгоритма Дейкстры, которую я написал из псевдокода в Wikipedia article. Для графика с примерно 40 000 узлов и 80 000 ребер требуется 3 или 4 минуты. Это что-то вроде правильного порядка? Если нет, что случилось с моей реализацией?

struct DijkstraVertex { 
    int index; 
    vector<int> adj; 
    vector<double> weights; 
    double dist; 
    int prev; 
    bool opt; 
    DijkstraVertex(int vertexIndex, vector<int> adjacentVertices, vector<double> edgeWeights) { 
    index = vertexIndex; 
    adj = adjacentVertices; 
    weights = edgeWeights; 
    dist = numeric_limits<double>::infinity(); 
    prev = -1; // "undefined" node 
    opt = false; // unoptimized node 
    } 
}; 

void dijsktra(vector<DijkstraVertex*> graph, int source, vector<double> &dist, vector<int> &prev) { 
    vector<DijkstraVertex*> Q(G); // set of unoptimized nodes 
    G[source]->dist = 0; 
    while (!Q.empty()) { 
    sort(Q.begin(), Q.end(), dijkstraDistComp); // sort nodes in Q by dist from source 
    DijkstraVertex* u = Q.front(); // u = node in Q with lowest dist 
    u->opt = true; 
    Q.erase(Q.begin()); 
    if (u->dist == numeric_limits<double>::infinity()) { 
     break; // all remaining vertices are inaccessible from the source 
    } 
    for (int i = 0; i < (signed)u->adj.size(); i++) { // for each neighbour of u not in Q 
    DijkstraVertex* v = G[u->adj[i]]; 
    if (!v->opt) { 
     double alt = u->dist + u->weights[i]; 
     if (alt < v->dist) { 
     v->dist = alt; 
     v->prev = u->index; 
     } 
    } 
    } 
    } 
    for (int i = 0; i < (signed)G.size(); i++) { 
    assert(G[i] != NULL); 
    dist.push_back(G[i]->dist); // transfer data to dist for output 
    prev.push_back(G[i]->prev); // transfer data to prev for output 
    } 
} 

Answer 1

Есть несколько вещей, которые вы можете улучшить на этом:

• реализующей очередь приоритета с сортировкой и стирают добавляет фактор | E | во время выполнения - используйте heap functions STL, чтобы получить вложение и удаление журнала (N) в очередь.
• не ставьте все узлы в очередь сразу, а только те, где вы обнаружили a путь (который может быть или не быть оптимальным, поскольку вы можете найти косвенный путь через узлы в очереди).
• создание объектов для каждого узла создает ненужную фрагментацию памяти. Если вы заботитесь о том, чтобы выжать последние 5-10%, вы могли бы подумать о решении представить матрицу инцидентов и другую информацию непосредственно в виде массивов.

Answer 2

Использовать priority_queue.

реализация Моего Дейкстр:

struct edge 
{ 
    int v,w; 
    edge(int _w,int _v):w(_w),v(_v){} 
}; 
vector<vector<edge> > g; 
enum color {white,gray,black}; 
vector<int> dijkstra(int s) 
{ 
    int n=g.size(); 
    vector<int> d(n,-1); 
    vector<color> c(n,white); 
    d[s]=0; 
    c[s]=gray; 
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; // declare priority_queue 
    q.push(make_pair(d[s],s)); //push starting vertex 
    while(!q.empty()) 
    { 
     int u=q.top().second;q.pop(); //pop vertex from queue 
     if(c[u]==black)continue; 
     c[u]=black; 
     for(int i=0;i<g[u].size();i++) 
     { 
      int v=g[u][i].v,w=g[u][i].w; 
      if(c[v]==white) //new vertex found 
      { 
       d[v]=d[u]+w; 
       c[v]=gray; 
       q.push(make_pair(d[v],v)); //add vertex to queue 
      } 
      else if(c[v]==gray && d[v]>d[u]+w) //shorter path to gray vertex found 
      { 
       d[v]=d[u]+w; 
       q.push(make_pair(d[v],v)); //push this vertex to queue 
      } 
     } 
    } 
    return d; 
}