鉄道のシミュレータは、無向グラフで表され、エッジは列車のトラックであり、頂点はスイッチです。無向グラフのパスの衝突をテストするアルゴリズム
here is what the railway looks like
列車は両方の方向を駆動することができます各スイッチの間に一つだけのトラックがあります。
すべての電車について、Dijkstraの最短経路アルゴリズムを使用して方向を計算します。しかし、今私はその結果との衝突を検出することができる必要があります。例えば
だが、現在のトラックがGtを
された状態でかつB =（GKのLg NmのBxの2本の列車AとB
A =（GTのMx LgはNmでLG）は経路 があるとしようA1）
これらの列車が特定のポイントでお互いに衝突することは容易にわかります。私はこれを予測して防止する方法を探しています。
ユニオン検索やKnuthアルゴリズムxを調べましたが、あなたの誰かがこれを解決する良いアイデアを持っていることを願っています。
時間の制約によって興味がない場合は、ネットワークに適用された混合整数プログラミングを使用できます。
各列車には1つの出発地と1つの目的地があります。各列車の場合 ：
がネットワークを流れることができる1「製品」を作成します。
積を出力する、起点ノードで「ソース」を作成（容量で1）
次に、各エッジの容量を1に設定します。 各ソースおよびエッジを流れる製品は整数変数です。
次に、シンクを流れる製品の量を最大にするようにmaxflowソルバーに依頼してください。 これにより、ネットワーク上を循環できる列車の最大量、各列車が目的地に到達するために使用する経路を知ることができます。
この情報があれば、どのトラックを「ロック」するべきかを知ることができます。
ネットワークモデリングのためのリニア/混合整数計画：実装の詳細についてはhttp://home.ubalt.edu/ntsbarsh/opre640a/partIII.htm
、あなたはブートストラップすることはかなり簡単である、Googleやツールを使用して、Javaのために働くことができ、C＃の、C++：https://developers.google.com/optimization/
Pythonに行きたい場合は、次のポストを参照してください。Python Mixed Integer Linear Programming
アルゴリズムには時間を考慮する必要がありますか？列車ごとに速度がありますか？ – David
私はすべての電車の速度と、頂点までの距離を計算する関数を持っています。それができればそれはいいだろうが、それが考慮されて時間を取ることなく動作している場合私はすでに幸せだ。 – user3163085
ノードと離れたパスを探していますか？ –