この方法で Dijkstra'a Algorithm を変更できるかどうか疑問に思っていました: 2 つの頂点間に次の長さの 2 つのパスがあるとします。
5, 8, 6, 9 // sum=28
2, 4, 8, 25 //sum=39
最初のパスは短いですが、両方の最長エッジを無視すると、合計が 19 と 14 になるので、2 番目のパスを選択します。
ダイクストラを使用せずに、別の解決方法があるのでしょうか?
1 に答える
1
このアイデアがうまくいくかどうかはわかりませんが、最初はうまくいくように思えます。
訪問した各ノードについて、 distance の横に、そのノードD(n)へのパス上の最長エッジの長さ、たとえば を格納しますL(v)。未訪問の隣接ノードの距離はmin D(n) + L(n) - max(L(n), weight(v,n))、訪問済みのすべての隣接ノードに対してnです。がへのパス上の最後のノードである場合、L(v)次に訪問したノードの はです。同じ長さの(より多くの)へのパスが複数ある場合は、最大のものを選択します。max(L(n), weight(v,n))nvvn'sL(v)
于 2013-01-05T16:58:47.953 に答える