我怎样才能使对 Dijkstra 算法的这种修改更有效？

Question

这个问题是我计算机科学作业的一部分。家庭作业包括 5 种不同类型的 students，它们遍历给定的加权无向节点图，其中每个学生都有不同的方法。第五位同学是最难的，一直没能高效实施

The fifth student has a secret power, (s)he can teleport between adjacent nodes, so it takes 0 time to travel between them. However, to recharge that secret power, (s)he needs to pass two edges, and (s)he does not have that secret power at the beginning of his/her journey. Unlike other four students, (s)he can use the same edge multiple times, so in the first move, (s)he may go N_1->N_2 and N_2->N_1 to recharge his/her secret power. (S)he cannot store his/her secret power and must use it right away after after gaining it.

The fifth student wants to know the shortest time to reach the summit. At start, (s)he does not have any power, so (s)he needs to pass two edges to recharge it.

我尝试的方法是修改Dijkstra算法；它不是逐个节点移动，而是从一个节点计算所有三个可能的跳跃，只考虑前两个跳跃的权重。它考虑了所有情况，例如去到一个节点并返回充电电源并跳转一个高权重节点。它确实有效，我确实得到了给定测试用例的所有正确答案，但速度很慢。我们在两秒的限制下，现在我的算法对于具有 50 000 个节点和 100 000 个边的测试用例大约需要 4 秒。

我猜问题出在到达邻居的范围内，因为有 3 个嵌套的 for 循环可以到达所有可能的 3 个跳远邻居（同时还能够多次使用相同的边缘），这基本上使这个 O (n^3)（但我不太喜欢大哦符号，所以我不确定它是否真的是那样。）

有没有人有任何想法可以使这个算法更有效，或者其他算法不是那么慢？

感谢任何帮助！

如果对您有帮助，请提供代码。

long long int HelpStudents::fifthStudent() { 
auto start = std::chrono::system_clock::now();


set< pair<long long int,int> >setds;
vector<long long int> dist(totalNodes+15,std::numeric_limits<long long int>::max());
setds.insert(make_pair(0,1));
dist[1] = 0;
bool change = false;
int counter = 0;   //these variables were just for checking some things
int max_counter = 0;
int changed_summit = 0;
int operations_after_last_change = 0;


int w1;
int w2;
int db = 0;

vector<int> neighbors;
vector<int> neighbors2;
vector<int> neighbors3;
int u;

while(!setds.empty()){
    pair<long long int,int> tmp = *(setds.begin());
    setds.erase(setds.begin());
    u = tmp.second; //vertex label
    if(dist[u] > dist[summit_no]){
        continue;
    }
    if(!change){
        counter++;
    }else{
        counter = 0;  //debugging stuff
    }
    db++;
    //cout << db2 << endl;

    operations_after_last_change++;
    max_counter = max(counter,max_counter);
    //cout << "counter: " << counter <<endl;
    change = false;
    neighbors = adjacency_map[u];  //adjacency map holds a vector which contains the adjacent nodes for the given key

    //cout << "processing: " << "(" << tmp.first << ","<< tmp.second << ") " << endl;

    for(int nb : neighbors){
        w1 = getWeight(u,nb);  //this is one jump,
        //nb is neighboor
        neighbors2 = adjacency_map[nb];
        //cout << "\t->"  << nb  << endl;
        if( nb == summit_no){
            if(dist[nb] >  dist[u] + (w1)){

                auto t = setds.find(make_pair(dist[nb],nb));
                if(t != setds.end()){
                    setds.erase(t);
                }
                dist[nb] = dist[u] + (w1);
                change = true;
                changed_summit++;
                operations_after_last_change = 0;
                //cout << "changed summit to " << (dist[u] + (w1)) << endl;

                //continue;
            }
        }

        for(int nb2: neighbors2){  //second jump
            w2 = getWeight(nb,nb2);
            //cout << "\t\t->"  << nb2  << endl;
            if( nb2 == summit_no){
                if(dist[nb2] >  dist[u] + (w1+w2)){

                    auto t = setds.find(make_pair(dist[nb2],nb2));
                    if(t != setds.end()){
                        setds.erase(t);
                    }
                    dist[nb2] = dist[u] + (w1+w2);
                    change=true;
                    changed_summit++;
                    operations_after_last_change = 0;
                    //cout << "changed summit to " << (dist[u] + (w1+w2)) << endl;

                    //continue;
                }
            }
            neighbors3 = adjacency_map[nb2];

            for(int nbf: neighbors3){  //third jump, no weight
                //cout << "\t\t\t->"  << nbf;
                if(dist[nbf] >  dist[u] + (w1+w2)){


                    auto t = setds.find(make_pair(dist[nbf],nbf));
                    if(t != setds.end()) {
                        setds.erase(t);
                    }

                    change = true;
                    dist[nbf] = dist[u] + (w1+w2);
                    if(nbf == summit_no){
                        changed_summit++;
                        operations_after_last_change = 0;
                        //cout  << endl;
                    }else{
                        setds.insert(make_pair(dist[nbf],nbf));
                        //cout << "\t\t\t\t inserted ("<<dist[nbf]<<","<<nbf<<")"  << endl;
                    }

                    //cout << "changed " << nbf << " to " << (dist[u] + (w1+w2)) << ";  path: "<< u <<" -> "<<nb<<" -> "<<nb2 << " -> " <<nbf << endl;
                    //setds.insert(make_pair(dist[nbf],nbf));
                }else{
                    //cout  << endl;
                }
            }

        }





    }
}
auto end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
cout << "time passed: "<< elapsed_seconds.count() <<"   total loop: "<<db<< endl;
return dist[summit_no];

Answer 1

你制作（或更可能想象）一个新的有向图，其中每个唯一 situation/state 学生 5 可以在其中的节点 - 这是组合原始图形节点和电荷状态（0、1 或 2）。因为有 3 个电荷状态，所以这个图的节点数将是原来的 3 倍。

然后你在这个新图上使用完美的普通 Dijkstra 算法。

我怎样才能使对 Dijkstra 算法的这种修改更有效？

How can i make this modification on Dijkstra Algorithm more efficient?

algorithm

performance

c++11

graph-algorithm

processing-efficiency