[일반] 플로이드 워셜은 어떻게 되는거임?

[익명(175.223)]

시작점 경유점 도착점을 3개의 for문으로 한번씩 살피는건 알겠는데

순서 따라서 최소값이 리셋 안될수도 있을거 같은데

왜 한번에 되는거임?

[p플랫(urd05)]

dist(i,j,k)=(i번째 점에서 j번째 점까지 k번째 점까지 만을 이용했을 때의 최단경로 길이)라고 dp식을 정의하고 k의 차원을 없애도 업데이트가 잘못 되는 경우도 없으니까 슬라이딩 윈도우로 2차원으로 줄이는 거임.

[익명(175.223)]

????

[pichulia(211.36)]

아하. 그냥 행렬인가? 싶어서 n^2 log n 을 돌리면 터지는 이유가 대략 이런거군요.

[익명(220.90)]

그래프를 1차원으로 나타내면 1-2-3-4-5의 정점이 있고 1에서 5까지 가는데 2,3,4을 순서대로 거쳐서 가야 가장 빠른 길이라고 할 때, 만약 경유점이 2,3,4 순으로 탐색되면 1-3-4-5, 1-4-5, 1-5가 차례대로 구해지고, 만약 경유점이 4,2,3 순으로 탐색되면 1-2-3-5, 1-3-5, 1-5 가 구해지는거임. 그래도 이해가 안 되면, 종이에 복잡한 그래프를 그리고 두 정점과 빠른 길을 정의하고 나서, 그 길 사이에 있는 경유점이 (무작위 순서로)탐색될 때마다 경유점에 이어진 두 정점을 잇는 가상의 간선을 새로 만들어보면 됨. 그게 플로이드 워셜이 작동하는 원리임.