tadakado https://blog.hatena.ne.jp/tadakado/ tadakadoの日記 https://tadakado.hatenadiary.org/ algorithm ruby BGL 今日は久しぶりに楽しい一日を過ごした。その理由は、一日中頭の体操をしていたから。 DFSや(たぶん)BFSで、複数の最短経路*1を出せそうだと分かったので、実際に実験をしてみた。 色々考えて見つけた方法は、vertexでなくてedgeで探索木を構築すること。 これって、昔、研究室で学んだgSpanのアイデアに似ている。 ちなみに、探索木を完全に構築すると、最短経路だけでなく、全ての可能な経路を見つけたことになる。 しかし、とても時間がかかるので、深さを制限するとそれなりに使えることが分かった。 実際の実装は、ruby + rgl + Boost Graph Library. rubyで書くと非… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftadakado.hatenadiary.org%2Fentry%2F20080711%2F1215793384" title="Shortest paths by BFS (and DFS) - tadakadoの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-07-11 01:23:04 rich https://tadakado.hatenadiary.org/entry/20080711/1215793384 1.0 100%