下面是我根据 Wikipedia article 中的伪代码编写的 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
}
}
最佳答案
您可以对此进行改进:
- 用排序和删除实现优先级队列增加了一个因子|E|到运行时 - 使用 heap functions STL 的 log(N) 插入和删除到队列中。
- 不要立即将所有节点放入队列中,而只将那些您发现路径的节点放入队列(这可能是也可能不是最佳路径,因为您可以找到通过节点的间接路径队列)。
- 为每个节点创建对象会产生不必要的内存碎片。如果您关心挤出最后 5-10%,您可以考虑一种解决方案,将关联矩阵和其他信息直接表示为数组。
关于c++ - Dijkstra 算法实现的性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6319149/