アルゴリズムの記事
-
Rubyでダイクストラ法（ヒープを使わない版）の続き。Graphはベルマン-フォード法のとこで作ったもの、最小ヒープは先日作ったものを使う。 今度は最小ヒープを優先度付きキューとして使って実装した。 コード 優先度付きキ...
-
優先度付きキューとして使うための最小ヒープ。 常に最小の値が先頭に来るため、最小の値を素早く取り出すことができるデータ構造。計算量はO(1)と極めて軽い。 pushで追加して、popで取り出し。pushした場合もpopし...
-
ダイクストラ法はベルマン-フォード法と同じくグラフの最短路問題を解くアルゴリズム。ベルマン-フォード法がすべての辺に対して計算を繰り返すのに対して、ダイクストラ法ではコストが最小の頂点をたどって行くために効率的で計算量が...
-
グラフの最短路問題を解くアルゴリズム。アルゴリズム図鑑とWikipediaを参考にRubyで実装してみた。辺に重みのついた有向グラフに対して。 概要 コード グラフの実装が違うとまた違った実装になるだろう。 負の閉路はど...
-
独学コンピューターサイエンティストやアルゴリズム図鑑を始点に今更ながらアルゴリズムやデータ構造について学んでいるので、その流れでRubyでクイックソートを実装してみた。 他のソートの実装に比べるとやっぱクイックソートはち...
