このpdfをMSSP（複数ソースの最短経路）を構築しようとしていると見ていますが、相互に依存するツリーを構築する方法についての知識が不足しています。今まで私はスパニングツリーを作成したので、plannarグラフが作成されましたが、どうやってそのデュアルを構築するのかわからないので、行き詰まりました。これを解決するのに役立つ特定のアルゴリズム/アプローチまたは論文はありますか？私が検索したところ、何も役に立たなかった。
質問する
903 次
1 に答える
1
まだ持っていない場合は、組み合わせの埋め込みが必要です。接続構造からアルゴリズムを取得するための効率的なアルゴリズムがありますが、平面グラフの自然なソースには通常、自然な埋め込みがあります。埋め込みを表す方法はたくさんあります。同じ頭の頂点で反時計回りの順序で各ハーフエッジを次のハーフエッジにマッピングする順列πを使用しました。各（分離されていない）頂点には、循環してリンクされた入力ハーフエッジのリストが関連付けられています。
revを、ヘッドとテールの頂点が反対の、各ハーフエッジを他のハーフエッジにマップする順列とします。双対グラフの埋め込み順列は、πとそれに続くrevの合成です。各ハーフエッジを面の次のハーフエッジに時計回りの順序でマップします（または、裏側を見ているため、無限の面では反時計回りにマップします）。いくつかの例を手作業で試してみると、これはより明確になります。
最初のルートから最短経路を計算した後（私はダイクストラを使用しました。MSSPの実装が私のものよりもはるかに高速でない限り、漸近的に高速なアルゴリズムを使用しても相対的な改善はあまりありません）、深さ優先探索を実行します。最短経路ツリーに属するエッジは無視されます。（別の方法は、オイラーツアーの順序でインターデジタルツリーのハーフエッジを訪問することですが、このアプローチでは、余分な対数時間の動的ツリー操作が発生するように見えました。）
于 2013-03-07T14:45:09.997 に答える