ベルマン−フォード・アルゴリズム（Ruby） - Camera Obscura
ベルマン−フォード・アルゴリズムは、ダイクストラ法にさらに辺の重みが負の場合も含めて最短経路を求めることができます。入出力などはダイクストラ法の場合を参照して下さい。 コーディングは Ruby で行いました。返り値は配列 [shortest, pred] で、pred を見ると最短経路がわかります。 bellman_ford.rb def bellman_ford(g, s) h = g.map {|x| [x[0], x[1].keys]}.to_h shortest = Hash.new(Float::INFINITY) pred = {} shortest[s] = 0 (h.size - 1).times do h.each do |k, v| v.each do |x| if (a = shortest[k] + g[k][x]) < shortest[x] shortest[x
Railsで木構造を扱うには｜TechRacho by BPS株式会社
また以下のような、根ノード（親を持たないノード）や葉ノード（子を持たないノード）や世代をキーとしたmapを取得するクラスメソッドが使えるようになります。 Comment.roots # => [[隣接リスト最高！],[こんにちは]] Comment.root # Comment.roots.first と同じ # => [隣接リスト最高！] Comment.leaves # => [[シンプルでいいですよね],[入れ子集合モデルの方が良いですよ], [こんにちは。]] Comment.generations # => {0=>[[隣接リスト最高！],[こんにちは]], # 1=>[[シンプルでいいですよね],[アンチパターンですよ、経路列挙モデル使いましょう]], # 2=>[[入れ子集合モデルの方が良いですよ]]} またインスタンスメソッドでいえば、#parentで親ノード、#ances
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
