[그래프 탐색] 플로이드 와샬

언제 쓰이는가? 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 모든 최단 경로를 구하는 문제 플로이드 와샬이란? 다익스트라 알고리즘과 비슷하지만 출발 정점이 따로 필요 없다는 점 음의 가중치를 가지는 간선을 쓸 수 있는 점 모든 정점에 대한 경로를 계산하기 때문에 거리를 저장하는 자료구조는 2차 배열이 된다. 핵심 아이디어 → '거쳐가는 정점' 을 기준으로 최단 거리를 구한다. 플로이드 와샬 알고리즘 동작 원리 거리를 저장하는 테이블 Distance A B C D E A 0 INF INF INF 7 B 4 0 INF INF INF C 3 8 0 INF -4 D INF 3 -..

2020.09.20