書記が数学やるだけ#611 BFS法，DFS法，ダイクストラ法
今回は具体的なアルゴリズムを追っていく。
問題
説明
グラフを探索するアルゴリズムとして，幅優先探索法と深さ優先探索法が有名である。
2頂点間の最短距離を求めるには，ダイクストラ法が有効である。
解答
幅優先探索法
まず始点であるv1を記録し，それに接続しているv2,v3をキューに入れる。
次に，キューの先頭であるv2に訪問し，それに接続しているv4,v5,v6をキューに入れる。そうすると先頭はv3になるのでそこに訪問，接続している頂点は既に入っているので特に何もしない。
先頭であるv4に訪問，v7をキューに入れる。あとは同様にしてv5,v6,v7の順に訪問して，探索を終了する。
深さ優先探索法
まず始点のv1に訪問し，接続するv2,v3をスタックに入れる（今回は添字が小さい順に出すよう並び替えている）。
v2を取り出し，接続するv4,v5,v6をスタックに入れる。すると先頭はv4になるのでそこに訪問，接続するv7をスタックに入れる。
先頭であるv7を取り出し，あとは順にv5,v6,v3と取り出して探索を終了する。
ダイクストラ法
まず始点を0，それ以外を無限大と置く。次に，v1に接続するv2,v3について最短距離を更新する。
ここでv3の最短距離が1と確定する。次にv3に訪問，v6の最短距離を更新する。
ここでv6の最短距離が3と確定する。次にv6に訪問，v2（v1→v2より短い）v5の最短距離を更新する。
ここでv2の最短距離が4と確定する。次にv2に訪問，v4,v5の最短距離を更新する。
ここでv5の最短距離が6と確定する。次にv5に訪問，v4,v7の最短距離を更新する。
ここでv7の最短距離が7と確定する。次にv7に訪問，v4の最短距離を更新する。
ここでv4の最短距離が8と確定する。これで探索を終了する。
最後にダイクストラ法が使えないグラフの例について，これは負の重みを持つ場合が相当する。仮に最短距離が短い順に訪問したとしても，負の重みによりそれが最短であることが保証されなくなるからである。この場合は，ベルマン–フォード法やワーシャル–フロイド法を用いる必要がある。
本記事のもくじはこちら：
