動的なプログラミングですべてのペアの最短経路は

Question

すべて、

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

は 重み付き隣接行列の掛け算自体を考えてみましょう - この場合には、我々は 最小化によって添加することにより、行列乗算で乗算演算 を交換し、加算演算、以外。重み付けされた隣接行列 の積は、ノードの任意の対の間に長さ2 の最短パスを含む行列を返します。

この引数から、Aのn乗はすべての最短パスを含むことになります。

質問番号1：

私の質問のグラフでは、我々はどのような基準で長さの「n」のパスの議論の著者である、パス内の2つのノード間の最大n-1縁で持つことになるということです？それは以下のように言及されているスライドのスライド10に

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

後

。

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からCormenらの著書において

を式2を締結する方法、以下のように記載されています重みδ（i、j）？グラフに負の重みサイクルが含まれていない場合、最短パスはすべてシンプルであり、最大でn-1のエッジを含みます。頂点iから頂点jまでの経路が、n-1以上の辺を有する場合、iからjまでの最短経路よりも重みを小さくすることはできない。したがって、実際の最短経路重みは、

によって与えられる。ここで、d（i、j）=（i、j）power（n-1）=（i、j）power（n）=（i、j）power質問3：上の方程式では、著者がn-1以下のn-1個の辺を持ち、どのように上の代入が働くのか？

ありがとうございます！

Answer 1

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が直接EQ1から来ていません。式2は、第1式からの第2項に過ぎない。私はこれが書式設定またはコピーペーストエラーであると推測します（私はあなたのpptリンクが壊れていることを確認できません）

3. 著者は、n-1個以上のエッジを追加することによって何も得られないパスに：あなたは安全に（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) 
   ... 
   

   です。 （これは明らかですが、教科書はここに厳密な点があります...）

Answer 2

グラフでは、パスの2つのノード間にn-1エッジがありますが、作成者は長さ「n」のパスについてどのような議論をしていますか？あなたが議論されている複数の測定混乱している

：

• A^N長N頂点間（重量） "最短経路" を表します。
• "最大でn-1 2ノード間のエッジ" - この場合、グラフのサイズとしてnと考えています。

グラフは、頂点の数百を有することができるが、あなたの隣接行列A^3はN対策3.異なる長さの最短経路を示しています。