私は、問題に対する最短経路または最適/最適解を見つけるための多くのアルゴリズムとアプローチを発見しました。しかし、私がしたいのは、ある点から別の点までの最初のK最短経路を見つけるアルゴリズムです。私が直面している問題は、各ステップであなたが取るときに、その重みを持つ複数のオプションがあるときに、木を探索するようなものです。どのような種類のアルゴリズムがこの種の問題に対処するために使用されていますか？Kファーストショートパスアルゴリズムの検索
ホセ・サントス によるthe 2006 paperがあり、3つの異なるK最短経路探索アルゴリズムを比較しています。
円のアルゴリズムの実装： http://code.google.com/p/k-shortest-paths/
簡単なアルゴリズム&議論： Suggestions for KSPA on undirected graph
編集：私は、私は新しい質問に答えていたと思ったので、どうやら私は、リンクをクリックしました。非常に可能性が高いので、これを無視してください。この質問はあなたにとって重要ではありません。
問題の制限されたバージョンでは、これは実装するのがはるかに簡単になります。注意すべき最も重要なことは、ツリーでは、最短パスが2つのノード間の唯一のパスであることです。だから、あなたはn BFS traversalsを実行して、ツリー内のO(n²)であるすべてのペアの最短パスを解決してから、kの最小値を取得します。これはおそらく何らかの方法で最適化することができますが、これを行うための素朴なアプローチは、O(n² log n)時間でO(n²)の距離を並べ替えて、kの値を最小にすることです。いくつかの本を保つことで、時間の複雑さのオーバーヘッドなしに、どの距離がどのパスに対応しているかを把握することができます。これにより、O(n²)可能なs-t-pairにKSPAアルゴリズムを使用するよりも複雑になります。
あなたが実際にソースを固定し、そのソースからの距離が最小のkノードを取得している何を意味するのか、1 BFSが行います場合。ソースとターゲットの両方を修正することを意味する場合は、1つのBFSでも十分です。
私はあなたが下のレベルのノードからノードへ行くすべてのエッジがツリーの構造についての詳細を知らなくても、同じ重みを持っているという事実をどのように使用できるか表示されません。
私が見る限り、最短経路探索アルゴリズムで提案されている解決策は、一般的にグラフを扱っています。しかし、私が直面していることは、各ステップで、同じレベルのすべてのノードに対して同じオプション（同じ重みを持つ）を取る、ツリー内の最短パスを見つけることに関連しています。 – Fungsten