http://depth-first.com/articles/2008/11/22/casual-saturdays-complexity

今日は久しぶりに楽しい一日を過ごした。その理由は、一日中頭の体操をしていたから。 DFSや(たぶん)BFSで、複数の最短経路*1を出せそうだと分かったので、実際に実験をしてみた。 色々考えて見つけた方法は、vertexでなくてedgeで探索木を構築すること。 こ…

最短経路が複数あるときどう探すのか興味があって調べてみた。 ちなみに"複数の最短経路"では求めるページは見つからず、 "shortest path same"でヒットしたwikipediaに書いてあった。 英語を使わないと世界が広がらないと、またも実感。 wikipediaのDijkstr…