1

正の重み、有向、非巡回のグラフG =（V、E）が与えられます。sからtへのkエッジ最短経路を報告するためにO（k（m + n））で実行されるアルゴリズムを設計します。kエッジの最短パスは、sからtまでのk個のエッジを持つパスとして定義され、パスの合計の重みも、sからtまでのすべてのパスで最小である必要があります。

BFSを単独で使用して最短パスを見つけることはできないため（重みが等しくない限り）、実行時間はBFSを使用してk個のエッジを持つパスを見つけることを意味すると思います。私を失望させているのはkです。これは、BFSをk回実行することを意味すると思います。

私の考えられるアイデアは、ソースからBFSを実行して、考えられるすべてのkリンクパスを見つけることです。途中でレベルを追跡し、キューに追加するときに各ノードへの合計パスの重みを保存することで、考えられるすべてのk-linkパスとその重みを見つけることができます。明らかに、パスの重みが小さい、より低いレベルで宛先に遭遇した場合、定義上、kエッジの最短パスはありません。総重量が少ないk個を超えるエッジを持つパスがある場合はどうでしょうか。また、O（k（m + n））ではありません。役立つヒントをいただければ幸いです。

4

1 に答える 1

4

を からへの i- linkf[i][j]最短経路とします。最初はsj

f[1][x] = e(s, x);

次に、を計算するためK - 1に使用する各ラウンドを繰り返します。これは、f[i][]f[i + 1][]

for each node v:
    f[i + 1][v] = INF;
for each edge e[u][v]:
    f[i + 1][v] = min(f[i + 1][v], f[i][u] + e[u][v]);

したがってかかりますO(k(n + m))。

于 2013-03-14T01:31:46.587 に答える