駅名でしりとりしながら目的地に着く最短経路を探索します (JR のみ) 。
http://dame.dyndns.org/misc/shiritrain/
例えば東京から池袋は、山手線一本ではなく、東京 → 鶯谷 → 西大井 → 池袋という愉快な経路を表示します。東京から秋葉原は東京 → 鶯谷 → 二宮 (神奈川) → 八尾 (大阪) → 邑久 (岡山) → 呉ポートピア (広島) → 秋葉原 (1779.0 km) となります。秋葉原は遠いですね。
swa さんの mars の路線データを使用させていただいています。
実装方法
やったことは大まかに以下の通りです (Tossy-2 にヒントを貰いました) 。
- 路線データを無向グラフとして Johnson のアルゴリズムを適用し、任意の駅間の最短経路を求める。
- 駅を頂点、しりとり遷移可能な駅間 (東京→鶯谷など) を辺とする有向グラフ (しりとりグラフ) を作る。辺の長さには 1 で求めた最短経路を用いる。
- 検索では、しりとりグラフに対して Dijkstra のアルゴリズムを適用して最短しりとり経路を求める。
実装は主に Ruby でテキストファイルベースでやりましたが、Johnson や Dijkstra のアルゴリズムは boost graph library のものを使いました。
元の路線データでは頂点 (駅) の数は 4582 、辺の数は 4757 でした。しりとりグラフの辺の数は 451009 でした (頂点の数は当然路線データと同じ) 。
興味深いルート
まず気になるのはしりとり最短経路が最長となる駅の組です。しりとりグラフに Johnson のアルゴリズムを適用したところ、喜入から厚床が最長と出ました。喜入 (きいれ、鹿児島) → 礼受 (れうけ、北海道) → 剣淵 (けんぶち、北海道) → 近文 (ちかぶみ、北海道) → 水橋 (みずはし、富山) → 島尾 (しまお、富山) → 邑久 (おく、岡山) → 呉ポートピア (くれぽーとぴあ、広島) → 厚床 (あっとこ、北海道) (6839.4 km) と、日本を 1 往復半くらいします。誰か実行してください。
ですが喜入から厚床はもともと鹿児島から行くルートなので、普通に行っても 2000 km くらいかかります。そこで「普通の最短距離」と「しりとり最短距離」の比が最大になるルートを求めてみたところ、長者原から原町 (駅間 0.7 km の隣同士の駅) でした。長者原 (ちょうじゃばる、福岡) → 留萌 (るもい、北海道) → 石狩沼田 (いしかりぬまた、北海道) → 高砂 (たかさご、北海道) → 五稜郭 (ごりょうかく、北海道) → 呉羽 (くれは、富山) → 原町 (はるまち、福岡) (4452.3 km) 。
謝辞
駅名しりとりで家に帰る - デイリーポータル Z に感動して作りました。JR 以外の路線データはないので新宿から中野坂上までのしりとり経路はわかりませんが、新宿から中野まで JR だけでしりとりすると新宿 → 国立 → 茅ヶ崎 → 菊名 → 中野でした。
また、繰り返しになりますが路線データには swa さんの mars のものを使わせていただきました (公開の許可をいただいています) 。ありがとうございます。これだけのデータに全然ミスが見つからないので驚愕しました。
