幅優先探索と最短経路

幅優先探索は、ある頂点 v から始め、まずこのノードを訪問し、訪問済みとしてマークします。次に、ノード v の未訪問の隣接ノード {vi,..,vj} を順番に訪問し、それらを訪問済みとしてマークします。その後、{vi,...,vj} の各ノードに対してノード v の訪問方法を繰り返し、すべてのノードが訪問されるまで続けます。

次の3つのステップに分けることができます：

  • （1）補助キュー q を使用し、まず頂点 v をキューに入れ、訪問済みとしてマークし、その後ループでキューが空かどうかをチェックします。
  • （2）キューが空でない場合は、キューの最初の要素を取り出し、その要素に関連するすべての未訪問ノードをキューに入れ、これらのノードを訪問済みとしてマークします。
  • （3）キューが空であれば、幅優先探索ですべてのノードを訪問済みであることを意味します。

下図に示すように、右側の青は 0 からノードを探索する順序を表し、下は 0 からの距離を記録しています。幅優先探索によって重みなしグラフの最短経路を求めることができることがわかります。

以下に、幅優先探索方式で探索を完了し、最短経路を求めるコードを示します。前のセクションのコードに基づいて、経路内のノードの順序を記録するグローバル変数 ord 配列を追加します。ord[i] は i ノードが経路内で何番目かを表します。同時にコンストラクタを調整し、隣接ノードを探索する際、未訪問のノードにアクセスするたびに ord[i] = ord[v] + 1 として距離を記録します。隣接リストの幅優先探索の時間計算量は O(V+E)、隣接行列の時間計算量は O(V^2) です。

...
// コンストラクタ, 経路探索アルゴリズム, グラフgraphのs点から他の点への経路を探索します
public ShortestPath(Graph graph, int s){
    // アルゴリズム初期化
    G = graph;
    assert s >= 0 && s < G.V();

    visited = new boolean[G.V()];
    from = new int[G.V()];
    ord = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
        ord[i] = -1;
    }
    this.s = s;
    // 無向グラフの最短経路アルゴリズム, sから幅優先探索でグラフ全体を探索します
    LinkedList<Integer> q = new LinkedList<Integer>();
    q.push( s );
    visited[s] = true;
    ord[s] = 0;
    while( !q.isEmpty() ){
        int v = q.pop();
        for( int i : G.adj(v) )
            if( !visited[i] ){
                q.push(i);
                visited[i] = true;
                from[i] = v;
                ord[i] = ord[v] + 1;
            }
    }
}
...

s 点から w 点までの最短経路の長さを確認します。s から w に到達できない場合は -1 を返します。

...
public int length(int w){
    assert w >= 0 && w < G.V();
    return ord[w];
}
...

Java サンプルコード

ソースコードパッケージのダウンロード：Download

src/サンプル/graph/ShortestPath.java ファイルコード：

package サンプル.graph;

import サンプル.graph.read.Graph;

import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;

/**
* 幅優先探索と最短経路
 */
public class ShortestPath {
    // グラフの参照
    private Graph G;
    // 開始点
    private int s;
    // dfsの過程でノードが訪問済みかを記録
    private boolean[] visited;
    // 経路を記録, from[i]は探索経路上でのiの前のノードを表します
    private int[] from;
    // 経路内のノードの順序を記録。ord[i]はiノードが経路内で何番目かを表します。
    private int[] ord;
    // コンストラクタ, 経路探索アルゴリズム, グラフgraphのs点から他の点への経路を探索します
    public ShortestPath(Graph graph, int s){

        // アルゴリズム初期化
        G = graph;
        assert s >= 0 && s < G.V();

        visited = new boolean[G.V()];
        from = new int[G.V()];
        ord = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this.s = s;
        // 無向グラフの最短経路アルゴリズム, sから幅優先探索でグラフ全体を探索します
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.push( s );
        visited[s] = true;
        ord[s] = 0;
        while( !q.isEmpty() ){
            int v = q.pop();
            for( int i : G.adj(v) )
                if( !visited[i] ){
                    q.push(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i] = ord[v] + 1;
                }
        }
    }

    // s点からw点への経路があるかどうかを照会します
    public boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }
    // s点からw点への経路を照会し, vecに格納します
    public Vector<Integer> path(int w){
        assert hasPath(w) ;
        Stack<Integer> s = new Stack<Integer>();
        // from配列を逆方向に辿ってsからwへの経路を探索し, スタックに格納します
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // スタックから要素を順に取り出し, sからwへの順序付き経路を取得します
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // s点からw点への経路を出力します
    public void showPath(int w){
        assert hasPath(w) ;
        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
    // s点からw点への最短経路の長さを確認します
    // sからwに到達できない場合は-1を返します
    public int length(int w){
        assert w >= 0 && w < G.V();
        return ord[w];
    }
}
その他の拡張