graph-theory - 有向グラフのある頂点から別の頂点への最短経路

Question

私のグラフは有向で非常に大きいです。グラフの頂点は町を表し、端は町から町へのバスの移動ルートを表します。目標は、ある頂点から別の頂点へのパスを見つけることです。アルゴリズムがバス間の転送時間を考慮に入れることは非常に重要です。

ダイクストラのアルゴリズムを使用しますが、グラフ全体から 1 つの方法を見つけます。頂点から頂点への「最良の」方法をいくつか見つける必要があります。「最高」とは、乗り換え時間が最短であることを意味しますが、これは最も重要なポイントではありません。

Answer 1

複数の最短経路を見つける必要がある場合は、この質問を参照してください。

Answer 2

転送期間はわかりませんが、ゴールドバーグ、サンダースなどの多くの人が行っている時間依存の高速道路階層作業があります。これはgoogle（dblp、または任意の科学e-lib）で検索できます。大陸サイズの静的データセットの場合、それらは数千倍高速であり、動的シナリオと静的シナリオの両方に対応しています。

Answer 3

バスを変更するための「転送時間」は重要な変数であり、グラフの余分な頂点として表すのが最も簡単です。エッジの重みがバス間の移動時間を表すと仮定すると、ノードとエッジを使用して 2 つのバス間の移動時間を表すこともできます。