接続ノードグラフ用に作業しているゲームで、より高速なパスファインディングメカニズムを導入しようとしています。ノードは、「ネットワーク」と「ルーター」の2つのタイプに分類されます。
この図では、青い円はルーターと灰色の長方形のネットワークを表しています。
各ネットワークは、接続されているルーターのリストを保持し、その逆も同様です。ルーターは他のルーターに直接接続できず、ネットワークは他のネットワークに直接接続できません。
ネットワークは、接続されているルーターを一覧表示しますルーター
は同じことをします
送信元と宛先が同じネットワークであるパスを除く、可能な送信元と宛先のネットワークごとに、交差するネットワークの数で測定されるパスをマップするアルゴリズムを取得する必要があります。私は今1つ持っていますが、パスをマップするのに約2秒かかるため、接続されているすべてのプレーヤーにとって非常に目立ちます。
現在のアルゴリズムは、深さ優先のブルートフォース検索（パスキャッシングを機能させるために約1時間でまとめられたもの）であり、通過した順序でネットワークの配列を返します。これが、非常に遅い理由を説明しています。より効率的なアルゴリズムはありますか？
ちなみに、これらの例のグラフには4つのネットワークがありますが、実際のグラフには55のネットワークと約20のルーターが使用されています。不可能なパスも発生する可能性があり、ネットワーク/ルーターのグラフの地形が変化する可能性があるため、パスキャッシュを再構築する必要があります。
このタイプのグラフに最適な結果を提供する可能性のあるアプローチ/アルゴリズムはどれですか？