algorithm - Djikstra-like算法的优化

Question

我尝试设计一个简单的算法来使用类似 Dijkstra 的算法访问图，但是当图非常大（超过 75000 个节点）时，它似乎没有优化。

这是我的代码

class lamp {

    int id;
    bool visited = false;
    list<lamp*> connected;
    int distance = INT_MAX;

public:
    void setVisited() {
        visited = true;
    }

    bool isVisited() {
        return visited;
    }

    void addCOnnected(lamp* l) {
        connected.push_back(l);
    }

    list<lamp*> getConnected() {
        return connected;
    }

    void resetVisited() {
        visited = false;
    }

    void setId(int i) {
        id = i;
    }

    void setDistance(int d) {
        distance = distance < d ? distance : d;
    }

    int getDistance() {
        return distance;
    }

};

void resetVisited(lamp* l, int n) {
    for (int i = 0; i < n; i++) {
        l[i].resetVisited();
    }
}

void evaluateDistance(lamp& l) {

    queue<lamp*> lampQueue;
    lampQueue.push(&l);
    l.setDistance(1);

    while (lampQueue.size() > 0) {

        lamp* current = lampQueue.front();
        lampQueue.pop();
        int currentDistance = current->getDistance();

        for (lamp* conn : current->getConnected()) {
            if (!(conn->isVisited())) {
                lampQueue.push(conn);
                conn->setVisited();
                conn->setDistance(currentDistance + 1);
            }
        }
    };
}

奇怪的 setDistance 是因为从不同的灯开始对任何灯的距离进行多次评估，并且在每个循环中保留最低的距离。

标签： algorithmoptimizationdijkstra