出発地から目的地までの最短の旅時間

Question

駅のリストを考えてみましょう。駅間の列車でつながっている「A」から「J」の10駅です。すなわち 各ステーションは任意ステーション直接または他の 介しから到達可能である、連結グラフを形成するためのステーション（頂点）と、それらの間 を実行列車（エッジ）を考慮し、グラフの点で

しかし完全ではありません、ホップすることによりステーション。最も重要なことは、これらのホップは、到着と出発の隣の間 待機が含まれています。間違いなく、接続された2つのステーション間の移動時間は、独立しています（ ）。ただし、 次の出発までの待ち時間は、到着した場所によって異なります。

注：私は理解を助けるためにグラフを述べます。一つは、それを超えて考えることができます。

問題：は、2つのステーションを考えると、最初の駅からの開始時間を、どのように、目的地までの最短時間を見つけるためにホップの場合は到着と出発の間の待機時間をカウント？同じDSにはどんなDSが使われますか？ 2つのステーションが列車で接続されている場合、それらの列車の間には列車が1つしかないと仮定します。

Answer 1

IMHO Dijkstraで十分です。

ノード "A"からDijkstraを実行すると、他のすべてのノードへの最短パスが検出されます。

「ホップ」がある場合でも、最悪の場合は、ある駅に早く行き、後で別のルートで後で同じ列車に入るのを待たなければなりません。

唯一の違いは、あなたが本当の「到着/出発」を有する列車によって引き起こされる

この動作だけ「の旅行の時間」の代わりに「旅の待ち時間+時間の時間」として価格を数えること、です。

すべてのノードの組み合わせA1 - > A2 - > A3のすべてのA2ノードの各ルートがA1からA3までランダムにペナルティを受ける場合、それは予測できないと思います。