Floyd - Warshall

모든 노드 간 최단 경로 탐색

- 음수 w 있어도 수행가능

- Dynamic programming 이용

 

단 하나의 맥락

- A~B 사이의 최단 경로 위에 K노드가 존재한다면, K로 들어가고 나오는 경로 역시 최단 경로

- D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

1

D[S][E](Adjacency matrix) 선언 후

> S == E일 때 0

> 나머지 = INF 

 

2

D[S][E] = W 저장

 

3

3중 for문의 형태로 반복 > 업데이트

for (k : 1~N) {

    for (S : 1~N) {

        for (E : 1~N) {

        D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);

        }

    }

}