obelisk2 https://blog.hatena.ne.jp/obelisk2/ Camera Obscura https://obelisk.hatenablog.com/ Ruby アルゴリズム 前エントリでは閉路なし有向グラフ（DAG）の場合に最短経路を求めてみましたが、ダイクストラ法は閉路があり、かつ辺の重みが非負の場合に最短経路を求めることができます。入出力は、閉路があって辺の重みが非負である以外、DAG の場合と同じなので、そちらを見て下さい。コーディングは Ruby で行いました。返り値は配列 [shortest, pred] で、pred を見ると最短経路がわかります。 dijkstra.rb def dijkstra(graph, start) h = graph.map {|x| [x[0], x[1].keys]}.to_h shortest = Hash.new(F… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fobelisk.hatenablog.com%2Fentry%2F2017%2F08%2F07%2F180132" title="ダイクストラ法（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/20170807/20170807175016.png Hatena Blog https://hatena.blog 2017-08-07 18:01:32 rich https://obelisk.hatenablog.com/entry/2017/08/07/180132 1.0 100%