2

加重グラフ G={V,E,ETW} があります。ここで、V はノード セット、E はエッジ セット、ETW はエッジ タイム ウィンドウのセットです。エッジ時間ウィンドウは 3 つのタプル (エッジ、開始時間、終了時間) であり、間隔 [開始時間、終了時間] で指定されたエッジが使用できないことを意味します。ここでの問題は、開始ノードから終了ノードまでの最短経路を見つけて、ノードで待機できるようにすることです (時間枠の後にエッジを使用するため)。

この問題のアルゴリズムを知っている人はいますか? (そして最良の場合、アルゴリズムが公開された論文)

4

1 に答える 1

0

エッジ値が非負であると仮定すると、これはやはりダイクストラのアルゴリズムです。少し変更するだけです。

次の変更を行う必要があります。現在のノード v に、エッジの時間ウィンドウのために許可されていない出力エッジ e がある場合は、現在のノードから時間ウィンドウの終わりに到達するのに必要な時間を追加します。瞬間（ノードvに到達した瞬間）をエッジの重みに。それ以外の場合、アルゴリズムは変更されません。

于 2012-04-19T08:52:48.673 に答える