3

全て、

すべてのペアの最短経路と行列乗算の関係について読んでいます。

加重隣接行列とそれ自体の乗算を考えてみましょう。ただし、この場合、行列乗算の乗算演算を加算に置き換え、加算演算を最小化に置き換えます。加重隣接行列とそれ自体の積は、任意のノード ペア間の長さ 2 の最短パスを含む行列を返すことに注意してください。

この引数から、A の n 乗にはすべての最短経路が含まれることになります。

質問番号 1:

私の質問は、グラフでは、パス内の 2 つのノード間に最大で n-1 個のエッジがあるということです。著者は、長さ「n」のパスについてどのような根拠で議論していますか?

次のスライド

www.infosun.fim.uni-passau.de/br/lehrstuhl/.../Westerheide2.PPT

スライド 10 では、次のように述べられています。

dij(1) = cij

dij(m) = min (dij(m-1), min1≤k≤n {dik(m-1) + ckj}) --> Eq 1
       = min1≤k≤n {dik(m-1) + ckj} ------------------> Eq 2

質問 2: 著者が式 1 から式 2 をどのように結論付けたか。

アルゴリズムの紹介に関するCormenらの本では、次のように言及されています。

実際の最短経路の重み delta(i, j) は? グラフに負の重みのサイクルが含まれていない場合、すべての最短パスは単純であり、最大で n - 1 個のエッジを含みます。n - 1 を超えるエッジを持つ頂点 i から頂点 j へのパスは、i から j への最短パスよりも重みを小さくすることはできません。したがって、実際の最短経路の重みは次の式で与えられます。

デルタ(i,j) = d(i,j) パワー (n-1) = (i,j) パワー (n) = (i,j) パワー (n+1) = ...

質問 3: 上記の式では、作成者は n, n+1 個のエッジをどのように作成しましたか? また、上記の割り当てはどのように機能しますか?

ありがとう！

4

2 に答える 2

4

  1. n 対 n-1 は、変数名の不運な選択です。より明確にするために、代わりに別の文字を使用する必要がありました。

    A^1 has the shortest paths of length up to 1 (trivially)
A^2 has the shortest paths of length up to 2
A^k has the shortest paths of length up to k

  2. 式 2 は式 1 から直接得られるわけではありません。式 2 は、最初の式の 2 番目の項にすぎません。これは書式設定またはコピーと貼り付けのエラーだと思います (確認できません - ppt リンクが壊れています)

  3. 著者は、パスに n-1 個以上のエッジを追加しても何も得られないことを明示的に指摘しています。

    A^(n-1),            //the shortest paths of length up tp (n-1)
is equal to A^n     //the shortest paths of length up tp (n)
is equal to A^(n+1) //the shortest paths of length up tp (n+1)
...

    これは、(n-1) で計算を安全に停止し、すべての長さのすべてのパスの中で最小のパスがあることを確認できるようにするためです。（これは当たり前のことですが、教科書はここで厳密であることに意味があります...）

于 2011-12-05T13:07:19.683 に答える
0

グラフでは、パス内の 2 つのノード間に最大 n-1 個のエッジがありますが、作者が長さ「n」のパスについて議論している根拠は何ですか?

議論されている複数の対策を混乱させています：

  • A^nは、頂点間の長さnの「最短パス」(重みによる) を表します。
  • 「2つのノード間の最大n-1エッジ」-この場合、nをグラフのサイズと考えていると思います。

グラフには数百の頂点がある可能性がありますが、隣接行列A^3は長さ 3 の最短経路を示しています。nの測定値が異なります。

于 2011-12-05T12:35:12.890 に答える