有向グラフと加重グラフで最も軽いパス ツリーを見つけるアルゴリズムを作成する必要があります。（可能な限り効率的であるべきです）私は頂点Sを取得しており、SからSからアプローチできるすべての頂点へのパスツリーを構築する必要があるため、ツリー内のパスは最も軽量です（パスの重みは端のないパスです)
最初に S からのすべての距離を計算することを考えました。次に、各パスに新しい重みがあります。重みから端点を引いたものです。次に、新しい重みを使用してグラフ上でダイクストラを実行します...
それはうまくいきますか？それは十分に効率的ですか？距離を計算する方法は？
あなたのコメントは、単一のソースからすべての頂点への最短経路を実際に探していることを示唆しています。
ダイクストラのアルゴリズムがどのように機能するかを見てみましょう。このアルゴリズムは、サイズ 1 のツリー (ソースのみ) から開始し、ツリーに頂点を繰り返し追加します。最終的に、ダイクストラのアルゴリズムによって作成されたツリーは、ソースからグラフ内の各ノードへの最短パスを表します。
ダイクストラのアルゴリズムはエッジに重み関数が必要ですが、重み関数は頂点にあることに注意してください。新しい重み関数を定義することで簡単に解決できますw':E->R:(w'(u,v) = w(u)終わりを数えたくないので機能します)。
最小のスパニング ツリーを求めているようです。ウィキペディアのページでは、アルゴリズムについて説明しています。