알고리즘 16-2

이전 내용을 코딩하자.

 

외부 변수에 배열 

입력: edge weight

 

아무것도 못거치는 건 weight값 넣어줌

(k=n-1까지는 이미 갖고 있는정보이므로 업데이트 순서는 상관없고 k만 새로 추가되어 업데이트)

 

 

---

 

위의 세 값을 이용해서 다른 층(밑의 그림)의 값을 정한다.

k번째 줄은 i,j가 바뀌는 경우에 재사용..(?)

 

 

 

인터넷에서는 D가 2차원 배열이다. => 바로 아래 층만 사용해서 답을 구하므로 메모리 줄이기 가능

k=0,2,4...일때 0번 배열에

k=1,2,3...일때 1번 배열에 번갈아가면서 저장하겠다!

 

스탠다드 작전. 메모리 n층을 안쓰고 2층만 쓰도록 바꿈!

 

 

---

 

책에서는 3차원 배열이 아예 없음!

원래 다른 층을 사용했지만 두 배열을 같은 배열로 구현해야 한다.

k를 계산할 때 k-1에 있는 값 3개를 이용했는데...

 

여기에서 계산하면 다른 값이 나온다.

어떤 때는 업데이트 된 값을, 어떤 떄는 업데이트 안된 값을 가져다 쓴다.

 

다행히 괜찮음. 항상 업데이트 된 값 = 업데이트 안된 값

D[k-1][i][k] = D[k][i][k]

(정의상&코드상으로 똑같다)

 

1. {1,2,...k-1}만 사용해서 i에서 k로 가는 가장 짧은 거리

2. {1,2...k}만 사용해서 i에서 k로 가는 가장 짧은 거리 => edge에는 k가 존재하지 않음!!

 

 

j가 k인 경우

(세번째) k에서 k로 가는 건 0이고

(첫번째)와 (두번째)는 D[k-1][i][k]로 아예 같은 값이므로 D[k-1][i][k] = D[k][i][k]

 

 

최종 정리된 코드