graph - k 個の頂点を訪れる無向グラフの最短経路

Question

無向グラフを考えてみましょう。n 個の頂点と m 個の辺があります。すべてのエッジには重みが関連付けられています。

入力としてソース頂点 's'、シンク頂点 't' および数値 'k' を受け取るアルゴリズムを考案したいと考えています。アルゴリズムの出力は、s から t までの最短経路であり、s と t の間に k 個の頂点があります。

提案してください。ありがとう！

Answer 1

少し調査した結果、この問題は NP-Hard であることがわかりました。したがって、この問題を解決するには、パラメータ化手法を使用する必要がありました。私が使用したアルゴリズムは、固定パラメーターの扱いやすいアルゴリズムです。

この問題を解決するために、アルゴリズムで円のアルゴリズムのローラーの修正を使用しました。Yen のアルゴリズムは、ループのないネットワークで最初の n 個の最短経路を見つけるのに役立ちます。私のアルゴリズムは次のようになります。

1. ユーザーからパラメーター k (パス内の頂点の数) を取得します。また、パスが超えてはならない最大距離である「m」をユーザーから取得します。これは、NP 困難な問題を多項式時間で解くのに役立つパラメーターです。

2. このステップでは円のアルゴリズムを使用します。次の最短経路を見つけます。パスに k 個の頂点があるかどうかを確認します。

   を。ある場合は、中止してパスを返します b. そうでなければ、2

3. パスの合計距離がパラメータ「m」を超える場合は、中止して「結果なし」を返します

Yen のアルゴリズムは、Dijkstra のアルゴリズムを使用して最短経路を見つけます。この問題を解決するためにこのアルゴリズムを実装するのは楽しかったです。

Answer 2

グラフに関連付けられた [numvertices][numvertices] の距離行列を作成します。次に、Floyd アルゴリズムを実行しますが、numvertices 反復の代わりに k 反復のみを実行します。