keyesberry https://blog.hatena.ne.jp/keyesberry/ hp12c https://keyesberry.hatenadiary.org/ 人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか次に同じ質問がきたときに 「1時間いらないっしょ、こんなの」 と是非ともほざくために 今から勉強します ダイクストラ法による最短経路探索 図におけるＳ点からＧ点に到達するための最短経路を求めたい 各ノードを結ぶエッジを糸としてＳ点をゆっくりと持ち上げた場合 緊張する糸が変移しながら最終的にＳ−Ｂ−Ｄ−Ｇを結ぶ糸が緊張して これが最短経路と分かる*1 計算機上でこの現象をシミュレートしたものを ダイクストラ法というらしい 今各ノードとそこから伸びるエッジの情報(コストと接続先)を渡して その最短経路および総コストを出力するプログラムを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkeyesberry.hatenadiary.org%2Fentry%2F20100121%2Fp1" title="Rubyで最短経路を探索しよう！ - hp12c" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/k/keyesberry/20100202/20100202222812.gif Hatena Blog https://hatena.blog 2010-01-21 00:00:00 rich https://keyesberry.hatenadiary.org/entry/20100121/p1 1.0 100%