ダイクストラのアルゴリズムを変更して、パス内のすべてのエッジ長の最大値が最小になる 2 つのノード間のパスを見つけることができるかどうか疑問に思っていました。
つまり、max(1,3,5,9) < max(10) であるため、単一のエッジ長 10 のパスよりもエッジ長 1,3,5,9 のパスが優先されます。
質問する
164 次
2 に答える
3
はい、これはダイクストラのアルゴリズムを使用して行うことができます
ヒント：各ノードuに、最小の重みwを格納します。これにより、訪問した頂点を通る、最大の重みがwであるsからuへのパスが存在します。上記の条件を満たすために、新しい頂点にアクセスするときに緩和条件を変更することを考えてください。
于 2012-09-16T03:26:28.783 に答える
0
d(u) が d(v)+c(u,v) によって更新されるのを覚えていますか? その代わりに、d(u) を max(d(v),c(u,v)) で更新するだけです。
別の解決策は、結果に対して二分探索を行うことです。特定の上限について、その上限に違反するエッジを削除してから、DFS/BFS で 2 つのノード s と t の間にまだパスがあるかどうかを確認できます。したがって、さまざまな上限を試して、二分探索で最も狭い上限を見つけることができます。
于 2012-09-16T09:50:14.647 に答える