obelisk2 https://blog.hatena.ne.jp/obelisk2/ Camera Obscura https://obelisk.hatenablog.com/ Ruby アルゴリズム 上の閉路なし有向グラフ（DAG）のように、辺に「重み」が付いている場合において、最短経路を求めてみます。手続きは 入力： G: n 個の頂点の集合 V と m 本の有向辺の集合 E を含む閉路なし有向グラフ。 s: V の始点。 出力： V に含まれる始点以外の頂点 v について、@shortest[v] は s から v への最短経路重み sp(s, v) であり、@pred[v] は何らかの最短経路上で v の直前にある頂点である。始点では、@shortest[s] = 0, @pred[s] = nil であり、s から v へのパスがない場合、@shortest[v] = ∞, @pr… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fobelisk.hatenablog.com%2Fentry%2F2017%2F07%2F31%2F182239" title="閉路なし有向グラフ（DAG）の最短経路（Ruby） - Camera Obscura" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://img.f.hatena.ne.jp/images/fotolife/o/obelisk2/20170731/20170731175854.png Hatena Blog https://hatena.blog 2017-07-31 18:22:39 rich https://obelisk.hatenablog.com/entry/2017/07/31/182239 1.0 100%