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

Question

私のグラフは非常に大きく、大きなグラフです。グラフの頂点は町を表し、辺は町から町へのバス旅行ルートを表します。目的は、ある頂点から別の頂点へのパスを見つけることです。アルゴリズムがバス間の転送時間を考慮することは非常に重要です。

私はDijkstraのアルゴリズムを使用しますが、それはグラフ全体からわかり、一方向を見つけます。私は、頂点から頂点までの「最良の」方法のいくつかを見つける必要があります。 「ベスト」とは、最短の転送時間を意味しますが、これは最も重要なポイントではありません。

Answer 1

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

Answer 2

私は転送用語ではわかりませんが、ゴールドバーグ、サンダーなどのような多くの人が行った時間依存のハイウェイ階層の作業があります。Google（dblp、または任意の科学的e-lib）で検索できます。大陸サイズの静的データセットでは、数千倍の時間がかかり、動的シナリオと静的シナリオの両方に対応します。

Answer 3

複数の最短パスを見つける必要がある場合は、this questionを参照してください。