Priority First Search 順位優先探索

Dijkstra's Algorithm のオーダーは、O(|V|^2) (ノードの数の２乗)です。これは、u を S に追加するためのループ（|V| 回）の中で、u を選択するためのループ（|V| 回）を行っていることから、簡単に導くことができます。このオーダーは、隣接行列で実装しても、隣接リストで実装しても同じですが、疎なグラフに対しては隣接リストで実装すべきです。（以下のテーブルを参照して下さい）。

タイプ	演算回数	オーダー
隣接行列	|V|^2 + |V|^2	|V|^2
隣接リスト	|V|^2 + |E|	|V|^2

Dijkstra's Algorithm は、隣接リストによる実装と、Priority Queue (Heap) を応用することによって、効率化することができます。このアルゴリズムは、Priority First Search (順位優先探索) とも呼ばれ、以下のように実装します。

	グラフ G(V, E) のノード全体の集合を V、 source をスタート地点、 S を「 source から S 内の各ノード v への最短経路が必ず S 内にあるような、最短経路の部分的な解の集合」とします（Dijkstra's Algorithm 参照）。
	各計算ステップにおいて、V - S の各ノード v について、S 内のノードのみを経由した source から v への最短経路のコスト(距離)を d[v] とします。また、各ノード間のコスト（距離） (x, y) は、行列 M[x][y] に記録されているものとします。
1.	初期状態で、S は空です。 source に対して    d[s] = 0 source 以外の V に属する全てのノード v に対して    d[v] = ∞ と初期化します。
	d[v] をキーとして、V - S に属するノードを minimum heap として構築します。これを heap とします。
2.	heap から d[u] が最小であるノード u を取り出します。   u = heap.extractMin()
	u を S に追加すると同時に、u に隣接しかつ V - S に属する全てのノード v に対する値を以下のように更新します。
	d[v] = min( d[v], d[u] + M[u][v] )     d[v] が更新された場合は、heap を更新します。         heap.update( v )　(v から upheap を施します)
	この処理を S = V となるまで繰り返します。

Priority First Search のオーダーは、O((|V| + |E|)log|V|) となります。u を heap から取り出すために |V|log|V|、d[v] を更新するために |E|log|V| の演算回数が必要です。

Priority First Search のプログラム例を以下に示します。

class Graph{
    public:
    vector<vector<int> > adjList;
    vector<vector<int>::iterator> pos;
    
    Graph(){}
    Graph( int size ){ resize( size );}
    
    void resize( int size ){
        adjList.resize( size ); pos.resize( size );
        for ( int i = 0; i < size; i++ ) adjList[i].clear();
    }
    
    int size(){ return adjList.size(); }
    
    void insert( int i, int j ){
        adjList[i].push_back( j );
    }
    
    int next( int i ){
        if ( pos[i] == adjList[i].end() ) return -1;
        return *pos[i]++;
    }
    
    void reset( int i ){ pos[i] = adjList[i].begin(); }
    void reset(){ for( int i = 0; i < size(); i++ ) reset(i); }
};

class Heap{
    public:
    int size;
    int H[MAX + 1]; // heap buffer
    int index[MAX + 1]; // index of v in the heap buffer
    int *key; // keys for heap condition
    
    Heap(){}
    Heap( int size, int d[] ): size(size){
        key = d;
    }
    
    void construct(){
        for ( int i = 0; i < size; i++ ){
            H[i + 1] = i; // heap is 1 base not 0
            index[i] = i + 1;
        }
        for ( int i = size / 2; i >= 1; i-- ) downheap( i );
    }
    
    int extractMin(){
        int v = H[1];
        H[1] = H[size];
        index[ H[size] ] = 1;
        size--;
        downheap(1);
        return v;
    }
    
    int update( int v ){
        upheap( index[v] );
    }
    
    private:
    void downheap( int k ){
        int j, v;
        v = H[k];
        while( k <= size/2 ){
            j = k + k;
            if ( j < size && key[ H[j] ] > key[ H[j+1] ] ) j++;
            if ( key[v] <= key[ H[j] ] ) break;
            H[k] = H[j];
            index[ H[j] ] = k;
            k = j;
        }
        H[k] = v;
        index[ v ] = k;
    }
    
    void upheap( int k){
        int v;
        v = H[k];
        while ( k > 1 && key[ H[k/2] ] >= key[v] ){
            H[k] = H[k/2];
            index[ H[k/2] ] = k;
            k = k/2;
        }
        H[k] = v;
        index[v] = k;
    }
};

int size;
int M[MAX][MAX];
Graph graph;

void dijkstra( int s, int d[] ){
    bool visited[MAX]; // S に属するノードは true
    for ( int i = 0; i < size; i++ ){
        d[i] = INT_MAX;
        visited[i] = false;
    }
    
    d[s] = 0; // 最初に s が u として選ばれる
    
    Heap heap = Heap( size, d );
    heap.construct();
    
    graph.reset();
    
    while( heap.size >= 1 ){
        int u = heap.extractMin();
        
        visited[u] = true; // u を S に追加
        
        int v;
        while ( ( v = graph.next( u ) ) != -1 ){
            if ( visited[v] ) continue;
            if ( d[u] + M[u][v] < d[v] ){
                d[v] =  d[u] + M[u][v];
                heap.update( v );
            }
        }
    }
}

このプログラム例ですと、自作の Heap を使っているので、プログラムが分かりづらくなってしまいました。私は、普段は自作の Heap を使うことはなく、以下のように既存の Priority queue に候補となるノードを突っ込んでいくアルゴリズムを実装しています。

class Graph{
    public:
    vector<vector<int> > adjList;
    vector<vector<int>::iterator> pos;
    
    Graph(){}
    Graph( int size ){ resize( size );}
    
    void resize( int size ){
        adjList.resize( size ); pos.resize( size );
        for ( int i = 0; i < size; i++ ) adjList[i].clear();
    }
    
    int size(){ return adjList.size(); }
    
    void insert( int i, int j ){
        adjList[i].push_back( j );
    }
    
    int next( int i ){
        if ( pos[i] == adjList[i].end() ) return -1;
        return *pos[i]++;
    }
    
    void reset( int i ){ pos[i] = adjList[i].begin(); }
    void reset(){ for( int i = 0; i < size(); i++ ) reset(i); }
};

class Node{
    public:
    int id, cost;
    Node(){}
    Node( int id, int cost ): id(id), cost(cost){}
    
    bool operator < ( const Node &n ) const{
        return cost > n.cost;
    }
};

int size;
int M[MAX][MAX];
Graph graph;

void dijkstra( int s, int d[] ){
    bool visited[MAX]; // S に属するノードは true
    for ( int i = 0; i < size; i++ ){
        d[i] = INT_MAX;
        visited[i] = false;
    }
    
    d[s] = 0;
    
    priority_queue<Node> PQ;
    PQ.push( Node( s, 0 ) );// 最初に s が u として選ばれる
    
    graph.reset();
    
    while( !PQ.empty() ){
        int u = PQ.top().id; PQ.pop();
        
        visited[u] = true; // u を S に追加
        
        int v;
        while ( ( v = graph.next( u ) ) != -1 ){
            if ( visited[v] ) continue;
            if ( d[u] + M[u][v] < d[v] ){
                d[v] =  d[u] + M[u][v];
                PQ.push( Node( v, d[v] ) );
            }
        }
    }
}

純粋に Heap を用いるのと比べて効率はやや劣りますが（なぜなら priority queue の中に余分なゴミが溜まっていくから）、オーダーがたかだか O((|V| + |E|)log|E|) になるだけなので、私の経験上、実用には問題ないようです。