플루이드워셜 k i j 순서가 궁금합니다.

큰돌님 안녕하세요?

플루이드 워셜 푸는데 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;
			}

回答 2

1

kundol

2024-10-23T01:35:34.575Z

ㅎㅎ 이해하셨군요

감사합니다.

1

mhyim

2024-10-22T17:09:55.878Z

k i j의 순서가 상관 없는게 아니라 i 와 j를 갱신하기 위한 중간 값이 k였습니다.

제대로 안 읽은건 나였고