Ниже представлена реализация алгоритма Дейкстры, который я написал на основе псевдокода в статье Википедии . Для графа примерно с 40 000 узлов и 80 000 ребер требуется 3 или 4 минуты для выполнения. Это что-то вроде правильного порядка величины? Если нет, что не так с моей реализацией?
struct DijkstraVertex {
int index;
vector adj;
vector weights;
double dist;
int prev;
bool opt;
DijkstraVertex(int vertexIndex, vector adjacentVertices, vector edgeWeights) {
index = vertexIndex;
adj = adjacentVertices;
weights = edgeWeights;
dist = numeric_limits::infinity();
prev = -1; // "undefined" node
opt = false; // unoptimized node
}
};
void dijsktra(vector graph, int source, vector &dist, vector &prev) {
vector 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::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
}
}