りゅうたい
735 ワード
りゅうたい
すべてのペアの最短経路のアルゴリズムを求めます
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];}
}
}
}```
Reference
この問題について(りゅうたい), 我々は、より多くの情報をここで見つけました
https://velog.io/@worldicate/플로이드
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
二次元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];}
}
}
}```
Reference
この問題について(りゅうたい), 我々は、より多くの情報をここで見つけました https://velog.io/@worldicate/플로이드テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol