マルチソース最短・floyd&&最小ループアルゴリズム

実は私はもうできます.のでも今日は一度書き間違えました...本当に怖いです.だから私はやはりこのfloydアルゴリズムを深く解析することにしました
Floyd-warshall
1.問題を出す
まず最も簡単な問題を並べて、あなたに図をあげて、aを尋ねて、bはaを求めて、b間は最も短絡します
floydができない时、私はしっかりと各点に対して単源の最短ルートを求めます...
後でfloydを習いました...floydは任意の2点間の最短ルートを求めます
2.floydアルゴリズムを与える

for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
	map[i][j] = min(map[i][j],map[i][k]+map[k][j]);
}

非常に簡潔なコード
3.解釈コード
先に宣言します:floydは1つの動態的な計画について
我々はopt[i][j][k]がi->jを表す1->kのみの点の最短路を定義する
では、kを過ぎていなければ、opt[i][j][k]=opt[i][j][k-1];
k opt[i][j][k]=opt[i][k][k-1]+opt[k][j][k-1];
そして総合するとopt[i][j][k]=min(opt[i][k][k-1]+opt[k][j][k-1]、opt[i][j][k]=opt[i][j][k]);
最後の次元kは圧縮できるようになり、opt[i][j]=min(opt[i][j],opt[i][k]+opt[k][j]);
floydはこんなに楽しく話しました~図無向図神馬の自分に変えました~
さいしょうループ
リング,,i,j,kは3点,リング長は3点2両ピッチ,
道路に交点がなく、
だから、map[i][j]+dist[i][k]+dist[j][k]
mapレコード最短,distレコード直接接続エッジ
map[i][j]でもk点でリングが出ても
最短k点にすぎない
floydのdp方程式を考えると
結局呼ぼうとしたでしょう~~私は言わないで、直接偽のコードに行きます

/*               。。*/
dist = map;
k = 1->n;
{
i = 1->k-1;
j = 1->i-1;
ans = min(ans,map[i][j] +dist[i][k] + dist[j][k] );//     i,j,k      ，       k-1,i-1。。。
i = 1->n;
j = 1->i;
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
}

これで、わからなかったり、異議があったり、新しい考えがあったりしたら歓迎討論しましょう~~