地下最短経路 - Java

Question

だから、私は2つの駅間の最短経路を見つけるプログラムを作りたいと思う。あなたが示唆しているのは、列車線を表す最も良い方法です。どこで交差して検索しますか？私の現在の考えは隣接行列またはリストですが、すべての隣接点がリンクされているわけではありません。

例： - ウォータールー、サザーク、ロンドンブリッジ

黒い線の駅 - ケニントン、オーバル、自治区、ロンドンブリッジ

ブラックライン2つの駅 - ケニントン、

• グレーラインの駅： 路線は次のようになります。ウォータールー、エンブレム
• 茶色の線の駅 - エレファント&城、ワーテルロー、堤防。私は、例えば、サザークにオーバルないしたい場合

、私は行くだろう：

• オーバルブラックライン上ケニントンその後（
• ケニントンウォータールーに（その後、空白行2を切り替える）へグレーラインに切り替える）
• ウォータールーtoサザーク。

Answer 1

これは、すべての可能なパスを試行する以外に、既知の解決策がない、トラベリングセールスマンの問題に似ています。このようなパスの数は、ステーションの数に応じて指数関数的に増加するので、計算上非常に高価になります。

また、駅間の最短距離、またはそれらの間の最短旅行時間を決定する必要があります。

Answer 2

これは最短経路の問題です。最短時間に興味があるので、距離の代わりに時間を使用してください。ダイクストラのアルゴリズムは、これらのタイプの問題を解決するための共通のアプローチです。それはインターネット上でよく書かれています。すべてのトリップの時刻表を生成する予定の場合は、Floyd-Warshallアルゴリズムを調べる必要があります。これは、すべてのステーションペアに対してソリューションを生成できるためです。

これらの方法では、レールシステムをグラフとしてモデル化する必要があります。エッジ重みは、ステーション間を移動する時間になります。複数の回線を持つステーションの場合、複数のノードとエッジの間に4の重みを使用できます。