アルゴリズムの記事
-
Rubyでダイクストラ法(ヒープを使わない版)の続き。Graphはベルマン-フォード法のとこで作ったもの、最小ヒープは先日作ったものを使う。 今度は最小ヒープを優先度付きキューとして使って実装した。 コード 優先度付きキ...
-
2022-12-25追記 Algorithmsと言うgemを見つけた。使いたいデータ構造があったらこれを使うのがよさげ。 2023-01-05追記 Algorithms gemのMinHeapはなんだか重い。中身をちょっ...
-
ダイクストラ法はベルマン-フォード法と同じくグラフの最短路問題を解くアルゴリズム。ベルマン-フォード法がすべての辺に対して計算を繰り返すのに対して、ダイクストラ法ではコストが最小の頂点をたどって行くために効率的で計算量が...
-
グラフの最短路問題を解くアルゴリズム。アルゴリズム図鑑とWikipediaを参考にRubyで実装してみた。辺に重みのついた有向グラフに対して。 概要 コード グラフの実装が違うとまた違った実装になるだろう。 負の閉路はど...
-
独学コンピューターサイエンティストやアルゴリズム図鑑を始点に今更ながらアルゴリズムやデータ構造について学んでいるので、その流れでRubyでクイックソートを実装してみた。 他のソートの実装に比べるとやっぱクイックソートはち...