[질문] 플로이드 와셜 알고리즘 관련질문

[건국우유(konkuk16)]

동빈나 플로이드 와셜관련 질문입니다

여기서 4 -> 2를 가는게 아무리 계산해봐도

inf 가 나오는데

inf가 안되는 방법은 4에서 3을 거쳐 1로 간다음 2로 가는

그 방법 밖엔 없는데

i j까지 k는 단 하나 밖에 없는데 어떻게 10이라는 값이 나오나요?

- dc official App

[0xrgb(0xrgb)]

?

[건국우유(konkuk16)]

이상하네요.. 앱에서 제가 쓴 글이 보이지를 않아요 - dc App

[건국우유(konkuk16)]

다른 마이너 갤러리에서 쓴 글은 잘만 보이는데 왜 여기서 쓴 글은 안보이지? 미치겠네 ㅡ;;

[0xrgb(0xrgb)]

답을 해주고 싶지만은 질문이 이해가 안간다 이 말이에요

[건국우유(konkuk16)]

아 그러니까 4 3 1 2로 가는게 최저치인건 알겠는데 중간에 있는 k가 오직 하나 밖에 없는데 어떻게 4 3 1 2로 가냐는거죠 - dc App

[건국우유(konkuk16)]

4 1 2 4 3 2가 전부 중간값이 inf 라서 .. - dc App

[0xrgb(0xrgb)]

일단 1을 중심으로 한번 루프를 돌음. 그러면 3->1->2의 경로가 있으니 3->2의 최단이 찾아짐. 그 이후 2 중심으로 돌고, 3 중심으로 돌면 4->3->2로 4->2의 최단이 찾아짐

[0xrgb(0xrgb)]

이게 이해가 안된다 하면은 플로이드 알고리즘을 잘못 이해한것이야

[건국우유(konkuk16)]

아 아 아 그러니까 3 2의 최소값을 토대로 계산을 수행하니 4 3 1 2값이 찾아 진다는거군요 감사합니다 - dc App

[건국우유(konkuk16)]

맨처음에 어떻게 찾아가나 스택에 저장이라도 되있나 했었는데 알고리즘이 돌면서 최소값을 저장해뒀으니 그대로 경로가 찾아가는거였네요 - dc App