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