2017-07-31から1日間の記事一覧

閉路なし有向グラフ(DAG)の最短経路(Ruby)

上の閉路なし有向グラフ(DAG)のように、辺に「重み」が付いている場合において、最短経路を求めてみます。手続きは 入力: G: n 個の頂点の集合 V と m 本の有向辺の集合 E を含む閉路なし有向グラフ。 s: V の始点。 出力: V に含まれる始点以外の頂点 v…

トポロジカルソート(Ruby)

閉路なし有向グラフ(DAG: directed acyclic graph)のトポロジカルソートです。トポロジカルソートとは、上のようなグラフがあったとき、 入力:1〜n の頂点をもつ閉路なし有向グラフ。 出力:グラフ内の辺を (u, v) とするとき、u が v の前になるように並…