離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃんということでやってみた。 pngファイルをアニメーションgifに変換するのはこんな感じで。この辺を参考に。 convert -geometry 320x500! -delay 150 -loop 0 bellman_ford_example_a_uniq*.png bellman_ford_example_a.gif 俺はRubyで書いたわけだけど、こんなことをやってるid:mickey24に「それRでできるよ!!」と言われそうである。 単一始点最短路問題に対するその他のアルゴリズムベルマンフォードのアルゴリズムは単一始点最短路問題に対する
![ベルマンフォードのアルゴリズムで実行される結果も逐次表示 - yasuhisa's blog](https://cdn-ak-scissors.b.st-hatena.com/image/square/971c0360728ea11049301dde9eaa4940af693aa2/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fs%2Fsyou6162%2F20090625%2F20090625154045.gif)