k-最短パスを見つけるためのアルゴリズムを知っている人はいますか?インターネットで検索して円を見つけましたが、とても複雑ですか?
本当にありがとう。
質問する
1053 次
3 に答える
3
効率的に (多項式に) 実行できない1 - 問題はNP 困難です
このように考えてみてください - ak の最短経路 (ここでは単純な経路を仮定します) の長ささえ多項式で見つける[1,n!]ことがkできますか?長さのパス）。n
ハミルトニアン経路問題は NP 困難であるため、この問題も NP 困難であり、既知の多項式解はありません。
(1)おそらく、P=NPでない限り、しかし、ほとんどの CS 研究者は、その可能性は非常に低いと考えています
于 2013-01-21T08:28:32.150 に答える
1
今ではすっかり...
Google for Djikstra のアルゴリズム。ここに実装があります。
于 2013-01-21T08:30:11.853 に答える
0
これは、ディスジョイント セットで解決されます。グーグルで検索しますが、要するに2つのベクトルがあります。-1 で初期化された親の 1 つ。もう 1 つはゼロで初期化されたランク用です。次に、ソース ノードから始めます。そこから取得できる可能性のある各ノードに移動します。親[i] =現在のノードにすることで、それらをセットに追加します。番号を保持するランク [i] に基づいて行われる、誰の親になるかの決定
于 2013-01-21T09:28:55.910 に答える