알고리즘 - 플로이드 와샬(Floyd warshall)

최단 경로 탐색 알고리즘.

 

다른 알고리즘은 출발점, 도착점을 지정해야만 구할수 있는 반면, 이 알고리즘은 모든 노드 사이의 최단거리를 구할수 있다.

 

1. 그래프를 인접행렬로 저장. 두 노드 사이의 간선이 두 개 이상인 멀티 그래프라면, 짧은거 하나만 저장.(최단경로니까.)

2. 노드간 연결이 없으면 무한대로 저장.

3. 특정 정점을 경우해서 가는 경로의 길이와 기존에 저장한 정점사이의 거리를 비교해 짧은쪽으로 갱신.

4. 3번에 사용한 방법을 모든 정점에 대해 경유지로 설정해서 값을 갱신. A,B,C,D 노드를 가진 그래프라면 A를 경유해 가는 경로, B를 경유해 가는 경로, C를, D를 경유해 가는 경로를 전부 확인해서 갱신한다는 뜻.