Shortest path

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

A more general problem would be to find all the shortest paths between source and target (there might be several different ones of the same length). Then instead of storing only a single node in each entry of previous we would store all nodes satisfying the relaxation condition. For example, if both r and source connect to target and both of them lie on different shortest paths through target (because the edge cost is the same in both cases), then we would add both r and source to previous[target]. When the algorithm completes, previous data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these short paths between two given nodes we would use a path finding algorithm on the new graph, such as depth-first search.

と書いてある。超訳すると、
ちょっと工夫すれば出来るが、そういう場合はDFSなど別のグラフで探そうぜ。
とのこと。なるほど、勉強になりました。
コストが全て1の場合は、BFSで探していくのが有効かな。DijkstraはBFS的だし。

キーワードが分かったところで、"最短経路 BFS"で検索してみると。
Boost Graph Libraryのページを発見。やはりこのライブラリかぁ。
rubyにもRにもラッパーのライブラリがあるみたい。