18강. 플로이드-와샬 알고리즘

[ 목차 ]

1. 플로이드-와샬 알고리즘

2. 중간 정점

3. 재귀해법

4. 수행과정

 

1. 플로이드-와샬 알고리즘

1) 각 간선의 값은 다음과 같이 표시

 

2) 최단 경로 행렬 d

3) 직전 정점 행렬

 

2. 중간 정점

1) 단순 경로 <v1, v2, ..., vi>가 있을 때, v1과 vi 사이에 있는 정점을 지칭

2) 플로이드-와샬 알고리즘은 중간 정점을 모두 실험

3) 정점 집합이 v = {1, 2, ..., n}이라고 하면 i, j가 v에 속할 때, i와 j 사이에 정점 집합 v에 속하는 모든 정점을 넣어보고 경로의 값이 가장 작아지는 경로를 찾음

4) 수행시간

 

3. 재귀해법

1) 정점 i부터 j까지 최단경로

2) {1, 2, ..., k}는 중간 정점의 집합

3) 얻어지는 재귀식

 

4. 수행과정