Dijkstra算法实现的性能

Question

以下是我从维基百科文章的伪代码中编写的Dijkstra算法实现。对于一个大约有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
  }  
}

- zoo

Answer 1

有几个方面可以改进：

• 使用排序和删除添加了|E|的因素，实现优先队列 - 使用STL的堆函数可以将插入和移除的时间复杂度降为log(N)。
• 不要一次性将所有节点都放入队列中，而只需放入已发现“一条”路径的节点（这可能是最优路径，也可能是通过队列中的节点间接找到的路径）。
• 每个节点创建对象会造成不必要的内存碎片。如果您关心挤出5-10%的性能提升，您可以考虑直接将关联矩阵和其他信息表示为数组的解决方案。

- Yannick Versley

---

谢谢您的回复。我得到的印象是，我的当前实现并不特别糟糕，而且根据您的建议，我可以期望在40,000个节点的问题上执行1-3分钟。30秒或1秒之类的执行时间是不合理的。这是真的吗？ - zoo

Answer 2

使用优先队列。

我的Dijkstra实现：

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;
}

- frp

---

我知道这篇帖子有点旧了。但是我不明白你想通过g[u].size()实现什么目的。你是想遍历g的邻接表吗？ - user1354510

g[u].size() 是与顶点 u 相连的顶点数量。 - frp