アルゴリズムのまとめ——Floyed

Floyed:
複雑度:O(n^3)
用途:1本の道がすべての地方の最小値を歩き終わることを求めて、とても簡単で、3つのforだけあって、普通はfloyedを書いてbellmanにお礼を言いませんford~~~
適用条件:すべての点を遍歴し、稠密図、floyed、bellmanに適しています.fordアルゴリズムの違いはfloyedが各点からの値を計算し、最後に選択すればいいので書きやすいが複雑度が高い
原理:隣接マトリクスで判断し、bellman_fordは1つの配列dを用いて判断する(実は互いに変換できるはずである--|)
手順:1.すべての辺を無限大に賦値し、通過できる賦値2.3つのforループ、k,i,j,kはi->jからi->k->jを歩くことができ、絶えず小さな値をとることを示す.出発点と終了点を選択すると、直接出力が最短になります
テンプレート:

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int  MAX = 300;

const int inf = 0x3f3f3f3f;

int d[MAX],map[MAX][MAX];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i = 1; i <= n ; i++)

        for(int j = 1; j <= n; j++)

          map[i][j] = inf;

    int x, y, t;

    for(int i = 1;i <=m;i++){

        scanf("%d%d%d",&x,&y,&t);

        map[x][y] = t;

    }

    for(int k = 1; k <= n ;k++){

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= n;j++){

                    if(i!=k&&i!=j)

                map[i][j] = min(map[i][j], map[i][k]+map[k][j]);

            }

        }

    }

    printf("%d",map[1][2]);

    return 0;

}