10

重み付きグラフ G(V,E) が与えられたとします。

グラフにはN個の頂点 ( 0 から N-1 までの番号が付けられています) とM 個の Bidirectional エッジが含まれています。

各エッジ (vi,vj)は正の距離 dを持ちます(つまり、2 つの頂点 vivj 間の距離は d です)。

任意の 2 つの頂点間には最大で 1 つのエッジがあり、セルフ ループもありません(つまり、頂点をそれ自体に接続するエッジはありません)。

また、 Sはソース頂点、Dは宛先頂点が与えられます。

Qをクエリの数とすると、各クエリには 1 つのエッジe( x ,y)が含まれます。

元のグラフにエッジ (x,y) がないと仮定して、クエリごとにソース S から目的地 D への最短経路を見つける必要があります。 S から D へのパスが存在しない場合は、No を出力する必要があります。

制約が高い 0<=(N,Q,M)<=25000

この問題を効率的に解決する方法は？

今まで私がやったことは、単純なDijakstra アルゴリズムを実装することです。

クエリ Q ごとに、(x,y) を Infinity に代入し、Dijakstra の最短パス を見つけるたびに。

ただし、全体的な複雑さがQ (Dijastra Shortes パスの時間の複雑さ) になるため、このアプローチは非常に遅くなります*

例：：

N=6,M=9
S=0 ,D=5

(u,v,cost(u,v))
0 2 4
3 5 8
3 4 1
2 3 1
0 1 1
4 5 1
2 4 5
1 2 1
1 3 3

Total Queries =6

Query edge=(0,1) Answer=7
Query edge=(0,2) Answer=5
Query edge=(1,3) Answer=5
Query edge=(2,3) Answer=6
Query edge=(4,5) Answer=11
Query edge=(3,4) Answer=8
4

3 に答える 3

3

最初に、ソース ノードから宛先への最短パス ツリーを計算します。

次に、すべてのクエリをループし、クエリで指定されたエッジで最短パスをカットします。これは最小カット問題を定義します。ここでは、ソース ノードと 1 つのパーティションのフロンティアの間の距離と、別のパーティションのフロンティアと宛先の間の距離があります。この問題は非常に簡単に計算できますが、せいぜいO(|E|).

したがって、このアルゴリズムでは が必要O(Q|E| + |V|log|V|)であり、 の場合、単純な解よりも漸近的に高速になり|V|log|V| > |E|ます。

このソリューションは Dijkstra の計算を再利用しますが、各クエリを個別に処理します。そのため、エッジによって引き起こされるカットの形状を観察することで、前のクエリで行った作業を連続するクエリで利用することにより、おそらく改善の余地があります。

于 2012-06-05T10:26:47.567 に答える
0

単純な最適化の 1 つ: 最初に完全なグラフ (エッジを削除しない) で Dijkstra を実行します。

次に、クエリごとに、要求されたエッジがその最短パスに属しているかどうかを確認します。そうでない場合 - このエッジを削除しても違いはありません。

于 2012-06-05T10:15:23.927 に答える