りゅうたい


りゅうたい


すべてのペアの最短経路のアルゴリズムを求めます
d[k][i][j]:iからjへの最短パスで、真ん中にアクセスできる頂点は{1,2,...,k}

パスにkがない場合


d[k-1][i][j]:kを使用しないため

kがパスにある場合


去i->kの最短経路と去k->jの最短経路では,中間にkは絶対にあってはならない.したがって
d[k-1][i][k]+d[k-1][k][k][j]の代わりに使用できます.
したがって、結果値はd[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])となる.

インプリメンテーション


二次元DPで実現できます.kも影響もない.
(cfリュックサック問題:d[i][j]i号品、重量がjの場合価値が最大、w[i],v[i])
d[i][j]=max(d[i-1][j],d[i-1]j-w[i]+v[i])->1次元配列を作成できます.(12865回)
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];}
}
}
}```