플로이드 워셜

1. 그래프의 최단 경로

그래프의 최단 경로를 구할 때

가중치가 없다면 아묻따 BFS를 하면 된다.

있다면, 

양의 가중치만 있다면 다익스트라

음의가중치도 있다면 벨만포드를 사용하면 됩니다.

플로이드 워샬 알고리즘도 음의 가중치를 허용합니다. '

 

2. 모든 쌍 최단 경로

이 문제의 초록색 경로처럼, 최단경로를 찾는 문제.

 

최단 경로 문제 예시

• 한 도시에서 다른 도시로 가장 빨리 갈 수 있는 경로 찾기
• 가중치 포함, 방향성 그래프에서 최단 경로 찾기
• 최적화 문제

---

brute-force 접근 방법

1. 한 정점에서 다른 정점으로의 모든 경로를 구한 뒤, 그들 중에서 최단 경로를 찾는다.
2. 그래프가 n개의 정점을 가지고 있고, 완전그래프라고 가정하면 
3. 한 정점 i에서 어떤 정점 j로 가능 경로들을 다 모아 보면, 그 경로들 중에서 나머지 모든 정점을 한번씩은 꼭 거쳐서 가능 경로들도 포함되어있는데, 그 경로들의 수만 우선 계산
4. i에서 출발하여 처음에 도착할 수 있는 정점의 가지 수는 n-2개고 그중에 하나를 선택하면, 그 다음에 도착할 수 있는 정점의 가지 수는 n-3개이고, 이렇게 계속하여 계산해보면, 총 경로의 개수는 (n-2)(n-3)...1 = (n-2)!가 된다.

이 경로의 개수만 보아도 지수보다 훨씬 크므로, 최단 경로 문제는 brute-foce를 사용하면 안된다!

---

플로이드-워셜 알고리즘(플로이드 알고리즘)

• 각 정점을 시작정점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행하여 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘
• 시간 복잡도가 O(n^3)으로, 다익스트라의 시간복잡도와 동일하다.
• 다익스트라의 모든 쌍 최단경로 버전이라고 생각하자.
• 매우 간단하여 다익스트라보다 효율적이다.