최단경로 - 3

Floyd-warshall 알고리즘 : all to all

- 가중치 방향 그래프 G=(V,E), V={1,2,...,n}

- 모든 노드 쌍들간의 최단경로의 길이를 구함

- d^k[i,j] : 중간에 노드집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이

 

i와 j가 바로 연결 

첫 번째 : 연결

두 번째 : 연결 x

n개의 노드가 있으므로 i에서 j로 갈 때 n개의 노드를 거쳐서 감

 

k를 거치지 않고 간다면 d^k-1[i,j]

k를 거쳐서 간다면 d^k-1[i,k] + d^k-1[k,i]

따라서 위의 두 값 중 최솟값을 고르면 된다.

 

수도코드 - 1

 

수도코드 - 2

 

경로 찾기

- 파이  이차원 배열을 만들어준다

- k를 거쳐서 가게 된다면 파이 배열에 k를 넣어준다

 

경로 출력하기

- i 에서 j까지 가는데 그 사이에 k를 경유한다면 i에서 k까지 출력하고 k에서 j까지 가는 방법을 출력한다.