関数を与えられた最小重みのパスを見つける

Question

私は無向グラフG = (V, E)、頂点sをVに、関数w:E->{0,1}を与えました。 vがVにあるとすれば、O(|V| + |E|)時間にsからvまでの最小重量を持つパスの重み（パスの重み=パスのエッジのワイトの和）を返す必要があります。
。
これは宿題のように聞こえるかもしれません。私は解決するのが面倒すぎます（私は時々これらの回答を得ています）。しかし、私はこの問題を解決するために本当に努力してきました。私のために持っているかもしれない。

Answer 1

この問題は、BFS algoのアナログでは解決できますが、キューの代わりにdeque（D）が使用されています。 Algoは各頂点に対してフラグが "マークされている"というリストを使用し、falseに初期化されます。 Sの距離が表示されるので、それらを保存したり、「オンザフライ」で使用したりできます。

Dはペア（頂点、距離ラベル）を格納します。

アルゴが開始：

Dは（S、0）によって初期化されます。

距離ラベルdのD（頂点v）の各頂点を抽出します。

vに既に到達したとマークされている場合は、次の繰り返しにスキップします。

それ以外の場合は、vに達したことを示します。ここで、dはsとvの間の正しい距離です。未到達の隣接（頂点w）ごとに距離ラベル（d_w = d + dist（v、w））を更新し、distの先頭にペア（w、d_w） （v、w）= 0、そうでなければ末尾に置く。

Algoが終了します。

すべての頂点に到達するとマークするときに、すべての頂点に距離を保存することができます。未到達の頂点はすべて無限遠の距離を持っています。

作業時間はO（| V | + | E |）です。各頂点と各エッジ（接続されたコンポーネントではs）を1回だけ処理するためです。

アルゴの正確さは、sとの距離による誘導によって証明することができます。