Floydアルゴリズム----5行のみのアルゴリズム

前に書いたDijkstraとは最短経路についてのアルゴリズムですが、Dijkstraアルゴリズムは単一ソース最短経路を計算するアルゴリズムで、つまり1点から他の点までの最短経路しか計算できません.Floydアルゴリズムは多ソース最短経路アルゴリズムで、任意の2点の最短経路を計算できます.
Floydについて話す前に、私たちが図(以下)に保存したと仮定して、私たちはどのように2点間の距離を短縮しますか?中継点として中間点しか見つからず、距離を短縮できることが明らかになった.この中間点は1つかもしれないし、2つかもしれないし、もっと多いかもしれない.
 
まず1を中間点として経路を短縮できるかどうかを見てみましょう
 
1
2
3
4
1
0
2
6
4
2
∞
0
3
∞
3
7
∞
0
1
4
5
∞
12
0
コード経由でやはり3つのポイントが短縮されました

for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
        if (map[i][j] > map[i][1] + map[1][j])
            map[i][j] = map[i][1] + map[1][j]

 
1
2
3
4
1
0
2
6
4
2
∞
0
3
∞
3
7
9
0
1
4
5
7
11
0
では、私たちは彼に1と2を中間点にしても短縮できるのではないでしょうか.それは1に基づいて判断することです

for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
        if (map[i][j] > map[i][1] + map[1][j])
            map[i][j] = map[i][1] + map[1][j]

for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
        if (map[i][j] > map[i][2] + map[2][j])
            map[i][j] = map[i][2] + map[2][j]

判断してまた2つの点が短くなりました
 
1
2
3
4
1
0
2
5
4
2
∞
0
3
∞
3
7
9
0
1
4
5
7
10
0
では、すべての点を転送点としてFloydアルゴリズムと判断し、完全なコードは以下の通りです.

#include
#define MAXN 999999;
int map[100][100];
void Floyd(int n){
	int k, i, j;
	for (k=1;k<=n;k++)//       
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
			if (map[i][j] > map[i][k] + map[k][j])
			map[i][j] = map[i][k] + map[k][j];
}
void init(int n){
	int i, j;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		if (i==j) map[i][j] = 0;
		else map[i][j] = MAXN;
}
int main (){
	int n, m, i, j, a, b, value;
	scanf("%d%d",&n,&m);
	init(n);
	for (i=0;i%d = %d
",i,j,map[i][j]);
}