Inflearn Community Q&A

큰돌님 안녕하세요?

플루이드 워셜 푸는데 k i j 순서가 의미가 있나 궁금해서 질문 드리게 되었습니다.

저의 생각은 "모든쌍에 대해 계산하므로 k i j 의 순서는 별로 상관 없다" 입니다.

그래서 코드를 이렇게 했더니 틀리더라구요?

	for(int k = 1;k<=n; k++)
	{
		for(int i = 1 ; i<=n;i++)
		{			
			for(int j = 1 ; j<=n;j++)
			{
			if(dist[k][i]==1 && dist[i][j] ==1) dist[k][j]=1;
			else if(dist[k][i]== -1 && dist[i][j] == -1) dist[k][j]=-1;
			}
		}		
	}

왜 큰돌님 해설 처럼 해야 하는지, 그리고 이 해설의 i k j? 순서로 해야하는지, 왜 그런지 차이가 궁금합니다.

for(int k=1; k<=n; k++)
	for(int i=1; i<= n; i++)
		for(int j=1; j<= n; j++){
                if(dist[i][k] == 1 && dist[k][j] == 1) dist[i][j] = 1;
                else if(dist[i][k] == -1 && dist[k][j] == -1) dist[i][j] = -1;
			}