Dijkstra算法实现的性能
|
以下是我根据Wikipedia文章中的伪代码编写的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
}
}
没有找到相关结果
已邀请:
2 个回复
课刊灭似
稳赣苍卯改
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; }