.. highlight:: c++

========================
グラフ関係のアルゴリズム
========================
ここでは最短経路問題を始めとするグラフ関係のアルゴリズムを紹介する。

ダイクストラ法
================
ダイクストラ法を用いれば負の辺を含まない単一始点最短経路問題を解くことが出来る。

ダイクストラ法では、未確定ノードの暫定コストが最小のものを順次確定させていく。暫定コストの更新は確定ノードが増えるごとにそれに隣接するノードについて確定ノードのコスト+辺のコストで更新される。ただし、それが元の暫定コストよりも小さいときに限る。

プライオリティキューを用いて実装出来る。暫定コストの更新があった段階でプライオリティキューにプッシュする。

.. literalinclude:: cpp/dijkstra/main.cpp

ベルマンフォード法
==================
単一始点最短経路問題で負の辺を持つ場合はベルマンフォード法を用いればよい。

これはダイクストラ法よりも単純で、始点のコストをゼロにしたあと、全辺の走査を行いながら頂点の更新をひたすら行っていく手法である。

.. literalinclude:: cpp/bellman-ford/main.cpp

ワーシャルフロイド法
=====================
全ての二頂点間の最短経路を求めるときにはワーシャルフロイド法が使える。

これは非常に実装がシンプルである。

.. literalinclude:: cpp/warshall-floyd/main.cpp

プリム法
==========
最小全域木を求めるにはプリム法を使えばよい。

まず好きな頂点を一つ選び、使用済みとする。そこから出てる全てのEdgeをプラオリティキューにpushする。これが初期化。

次にプライオリティキューからpopしてそこから繋る頂点を使用済とする。そこから出てる全てのEdgeをプライオリティキューにpushする。これを繰り返す。

.. literalinclude:: cpp/prim/main.cpp