2

指定されたコストを超えない最速のパスを見つけるのに問題があります。これと同様の質問がありますが、それらの間には大きな違いがあります。ここで、データに表示できるレコードは、低いポイントから高いポイントにつながるレコードだけです（たとえば、1-> 3が表示される場合がありますが、3-> 1は表示されない場合があります）（以下を参照）。それを知らずに、私はダイクストラを使います。その追加情報により、ダイクストラアルゴリズムよりも短時間で実行できる可能性があります。あなたはそれについてどう思いますか？

指定された最大コストと4つのレコードがあるとしましょう。

// specified cost
    10 
// end point
    5
//(start point) (finish point) (time) (cost)
    2 5 50 5
    3 5 20 9
    1 2 30 5
    1 3 30 7
// all the records lead from a lower to a higher point no.

ポイント（1）から（5）まで行くことができるかどうか（私たちが持っているよりもコストが<=のパスがない場合、または1-5の間に接続がない場合は不可能です）、もしそうなら、何をするかを決める必要がありますそこに入る最速の方法でしょう。

このようなデータの出力は次のようになります。

80 // fastest time
3 1 // number of points that (1 -> 2)  -> (2 -> 5)

1->2移動できるという記録がある場合は注意してください

1 2 30 5

2<-1を移動することはできません。

4

1 に答える 1

1

深さnの各ノードについて、そのノードへのパスの最小コストはn/2 * (minimal first edge at the path + minimal edge connecting to the node)-算術級数の合計です。この計算が必要な最大値を超える場合は、後続のノードをチェックする必要はありません。これらのノードを切り取り、残りにダイクストラを適用します。

于 2012-11-16T10:41:37.383 に答える