2

これが機能することを確認したいだけです。ダイクストラのアルゴリズムを使用して最大のパスを見つけることができますか？最初に距離を-1のようなものに初期化してから、relaxサブルーチンを変更して、それよりも大きいかどうかを確認する必要がありますか？

これは、負の重みがない問題の場合です。

これが実際の問題です。

電話網の図が与えられたとします。これは、頂点がスイッチの中心を表し、エッジが2つの中心間の通信回線を表すグラフGです。エッジは、最も低い帯域幅のエッジの帯域幅によってマークされます。ダイアグラムと2つのスイッチセンターaとbが与えられた場合、aとbの間のパスの最大帯域幅を出力するアルゴリズムを与えます。

これは機能しますか？

編集：

私はこれを見つけました：

ヒント：基本的なサブルーチンは、ダイクストラのサブルーチンRelaxと非常によく似ています。エッジ（u、v）があると仮定します。min {d [u]、w（u、v）}> d [v]の場合、d[v]をmin{d [u]、w（u、v）}に更新する必要があります（aからuからvへの帯域幅はmin{d[u]、w（u、v）}であり、これは現在の帯域幅よりも大きくなります）。

初期化時にはすべての距離が無限大であるため、それが何を意味するのか正確にはわかりません。だから、これがどのように機能するのかわかりません。手がかりはありますか？

4

6 に答える 6

1

Djikstraが行く方法かどうかはわかりません。負の重みは、Djikstraに悪いことをします。

エッジの重みで並べ替えて、最も低い重みのエッジ（最悪のボトルネック）を削除し、グラフがまだ接続されているかどうか（または少なくとも開始点と終了点）を確認できると思います。グラフが壊れているのは、ボトルネックを取り除いたことがわかっているときです。そのエッジの値を調べて、帯域幅を取得できます。（私が間違っていない場合、各反復にはO（E）時間がかかり、ボトルネックエッジを見つけるにはO（E）反復が必要になるため、これはO（E 2）アルゴリズムです。

編集：最大のパスは必ずしも最大の帯域幅ではないことを理解する必要があります。あなたはmin({edges in path})、ではなく、の値を最大化しようとしていsum({edges in path})ます。

于 2011-04-18T04:02:35.327 に答える
1

これは、ダイクストラ法を変更して他のすべての頂点への最大帯域幅を計算することで簡単に解決できます。

開始頂点を-1に初期化する必要はありません。

Algorithm: Maximum Bandwidth(G,a)

Input: A simple undirected weighted graph G with non -ve edge weights, and a distinguished     vertex a of G

Output: A label D[u], for each vertex u of G, such that D[u] is the maximum bandwidth available from a to u.


Initialize empty queue Q;
Start = a;
for each vertex u of G do,
   D[u] = 0;

for all vertices z adjacent to Start do{                              ---- 1

 If D[Start] => D[z] && w(start, z) > D[z] {
    Q.enqueue(z);
    D[z] = min(D[start], D[z]);
  }
}
If Q!=null {
   Start = Q.dequeue;
   Jump to 1

}

else
  finish();

これは帯域幅を計算するための最も効率的な方法ではないかもしれませんが、今のところ私が考えることができる方法です。

于 2012-04-17T18:21:33.940 に答える
0

ダイクストラのアルゴリズムを使用して、単一の最長パスを見つけることができますが、スイッチセンターが2つしかないため、ダイクストラのように各ノードにアクセスする必要がある理由がわかりません。分枝限定アルゴリズムなど、これを行うためのより最適な方法が最も好きです。

于 2011-04-18T04:07:46.103 に答える
0

フローの計算がより適切な場合がありますが、フローでは複数のパスを使用できます。

于 2011-04-18T04:00:56.823 に答える
0

エッジの重みを反転するだけです。つまり、エッジの重みがdの場合、代わりにd^-1と見なします。次に、通常どおりダイクストラ法を実行します。通常どおり、すべての距離を無限大に初期化します。

于 2011-04-18T04:04:31.727 に答える
0

アルゴリズムAllPairsShortestPaths（Floyd-Warshall）のロジックの一部を調整できますか？ http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm

接続されていないエッジを負の無限大に初期化し、距離の最小値を取る代わりに最大値を取りますか？

于 2015-03-28T16:51:06.140 に答える