c++でのダイクストラ法の実装

下記の優先度付きキューダイクストラ法のアルゴリズムの中に、用途のわからない記述があります。

c++
1void dijkstra(){
2    priority_queue<pair<int, int> > PQ;
3    int color[MAX];
4    int d[MAX];
5    for(int i=0; i<n; i++){
6        d[i] = INFTY;
7        color[i] = WHITE;
8    }
9
10    d[0] = 0;
11    PQ.push(make_pair(0,0));
12    color[0] = GRAY;
13
14    while( !PQ.empty() ){
15        pair<int, int> f = PQ.top(); PQ.pop();
16        int u = f.second;
17
18        color[u] = BLACK;
19
20        //最小値を取り出し、それが最短でなければ無視
21        if( d[u] < f.first * (-1) ) continue;
22
23        for(int j=0; j<adj[u].size(); j++){
24            int v = adj[u][j].first;
25            if(color[v] == BLACK) continue;
26            if(d[v] > d[u] + adj[u][j].second){
27                d[v] = d[u] + adj[u][j].second;
28                //priority_queueはデフォルトでは大きい値を優先するため‐１をかける
29                PQ.push(make_pair(d[v]*(-1), v));
30                color[v] = GRAY;
31            }
32        }
33    }
34
35    for(int i=0; i<n; i++){
36        cout << i << " " << (d[i] == INFTY ? -1 : d[i] ) << endl;
37    }
38}

fは優先度付きキューから取り出された値なので、常に（最短距離、ノード）の情報をもっていますよね。
それにもかかわらず、

cpp
1//最小値を取り出し、それが最短でなければ無視
2if( d[u] < f.first * (-1) ) continue;

となる状況がいまいち理解できません。
常に２つの値は等しいように思えます。

プログラムでは、この一文を入れても入れなくても正常に動作しました。
この一文の意味を教えていただけないでしょうか。

行動規範の内容に同意します

回答1件

ベストアンサー

そのコードが意味を持つのはこんな場合です。
最初スタートから到達可能なAとBがキューに入れられます。
最短距離が短いのはAなので、最初にAが取り出され、Cが最短距離6としてキューに入れられます。
その後Bが取り出され、Cの最短距離を4に更新してもう一度キューに入れます。
キューには最短距離4で入れられたCのノードと、最短距離6で入れられたCのノードが存在して、後者はその条件式ではじかれます。

そのコードの意味ですが、最悪のケースを想定すると同じノードが、入ってくるエッジと同じ数だけキューに追加されるうえ、それが出ていくエッジと同じ数だけ無駄にループを回すことになります。小さな問題では大した差はでませんが、大きな問題ではそのせいで数百倍の実行時間の差が出るケースも簡単に作れます。それを防ぐためにそのコードはあります。

投稿2020/04/17 09:08