모든 쌍의 shortest (길이만 구하기. 실제 path까지 구하는 것은 조금 어려우니 skip)
그래프에서 source가 정해지면 다른 노드로 가는 shortest path구하기
노드가 n개 있다면 출력할 값이 n^2개
1번에서 2번으로 가는 shortest path
2번에서 1번으로 가는 shortest path는 undirect냐 direct냐 에 따라 다르지만
undirect graph로 설명하겠다 => 같다
입력과 바로 매치가 안되서 어렵다.
* Dijkstra로 다 돌리면 시간이 O((m+n) log n)
보통 m>n이기 때문에 O(m logn)라고 표현 가능
(m: edge갯수 , n:node갯수)
모든 쌍의 Shortest Path구하기는
source node를 정하기 위해 이 과정을 n번 돌려야 한다.
=> O(n(m+n) log n)
이것보다 느리지 않지만 살짝 애매하다 (?)
m은 최대 n^2이다. (오늘 배울 것. 근데 annotation보단 실제가 훨씬 빠르다.)
=> O((n^3))
m이 작으면
=> O(n logn)
어떤 작전으로 풀 것인가?
노드는 1부터 N번까지 번호가 붙어있음.
k는 1씩 증가하면서 변할때, 노드 i에서 노드j로 가는 shortest path를 단계적으로 진행한다.
단, 1번부터 k번까지만 쓰는 shortest path를 구한다. (다 쓰는 것이 아니라 이 안에서 써야함)
ex)
i>10
j>10일때
k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다.
direct edge가 없다면 답은 무한대가 된다.
k=1이라면 1번 노드가 있다. {1}
(1번을 거쳐갈 수 있다.)
엣지가 없다면 못가는 거고 (무한대)
있다면 거쳐갈 수 있다.
하지만 안 거쳐가는 경우가 10으로 더 빠르므로 10
k=2라면 {1,2}
그냥 가는 방법 : 10
1만 거쳐 가는 방법: 12
2만 거쳐 가는 방법: 9
1,2를 거쳐 가는 방법: 8 (5+2+1)
2,1을 거쳐 가는 방법: 17
1번만 있을 때 1을 안썼다고 해서 2가 추가되었을 떄 1을 안쓰는 것이 답이 아니다.
k=0 답:10
k=1 답:10
k-2 답:8
초기값은 D[0][i][j]은 edge weight이다. 이차원 배열 w[i][j]
0<=k<n, 1<i=n, 1<=j<n
계산하는 값의 갯수가 n^3개
하나의 값을 상수시간에 계산하면 된다.
D[k][i][j]
= {1,2,...,k} 중에서 거쳐서 i->j 인 shortest path
계속 k를 증가시키며 D[k-1][i][j]을 통해 D[k][i][j]을 계산하겠다.
(1<i=n, 1<=j<n)
끝까지 가면 k=n일때 {1,2,3,...n} => 모든 노드를 가지고 만들어낸 shortest path
최종 답 = D[n][i][j]
(재사용이 되서 성능이 좋다.)
D[k-1][i][j]을 이미 가지고 있다.
노드i에서 노드j로 가는데 {1,2,...k}만 써서 갈 수 있는 제일 짧은 길을 찾아야 한다.
모르지만, k를 쓸 수도 있고 안쓸 수도 있다.
i부터 j까지 가는 shortest path에 같은 노드가 2번 쓰일 수 있나? ㄴㄴ
따라서 노드 k를 반드시 쓰는 shortest path => D[k-1][i][k]+D[k-1][k][j]
노드 k를 안쓰는 shortest path => D[k-1][i][j]와 같다.
둘 중 더 짧은 것이 정답이겠지! MIN( D[k-1][i][k]+D[k-1][k][j] , D[k-1][i][j] )
