本文介绍了Dijkstra算法实现的性能的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
以下是我在维基百科文章中的伪代码中写的Dijkstra算法的实现。。对于具有约40 000个节点和80 000个边缘的图,运行需要3或4分钟。这是什么像正确的数量级?如果没有,我的实现有什么问题?
Below is an implementation of Dijkstra's algorithm I wrote from the pseudocode in the Wikipedia article. For a graph with about 40 000 nodes and 80 000 edges, it takes 3 or 4 minutes to run. Is that anything like the right order of magnitude? If not, what's wrong with my implementation?
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 } }推荐答案
有几件事你可以改善:
- 使用排序和清除功能实现优先级队列的| E |到运行时 - 使用STL的堆函数获取日志(N)插入和删除到队列
- 不要立即将所有节点放入队列,而是只将那些已发现 路径的节点放置在队列中(这可能是最佳的,因为您可以找到通过队列中节点的间接路径)。
- 为每个节点创建对象会创建不必要的内存碎片。如果你关心挤出最后5-10%,你可以考虑一个解决方案直接表示矩阵和其他信息作为数组。
- implementing the priority queue with sort and erase adds a factor of |E| to the runtime - use the heap functions of the STL to get a log(N) insertion and removal into the queue.
- do not put all the nodes in the queue at once but only those where you have discovered a path (which may or may not be the optimal, as you can find an indirect path through nodes in the queue).
- creating objects for every node creates unneccessary memory fragmentation. If you care about squeezing out the last 5-10%, you could think about a solution to represent the incidence matrix and other information directly as arrays.
更多推荐
Dijkstra算法实现的性能
发布评论