다익스트라에 이어서 플로이드 워셜 알고리즘을 공부했다.
다익스트라를 모든 정점에서 돌리면 플로이드 워셜이 된다.
그런데 다익스트라는 음수 가중치를 가지는 간선이 있으면 안된다 한다.
플로이드 워셜은 모든 정점을 돌아보기 때문에 시간복잡도가 O(V^3)이다.
입력에서 중복값 확인을 해주니 정답이 됐다.
위키백과에 JAVA코드도 추가했다.
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 14852 타일채우기 3 풀이 (0) | 2017.10.18 |
|---|---|
| BOJ 2309 일곱난쟁이 풀이 (0) | 2017.10.18 |
| BOJ 2065 줄 세우기 (0) | 2017.10.18 |
| BOJ 1717 집합의 표현 disjoint-set (0) | 2017.10.17 |
| BOJ 1753 최단경로 다익스트라 알고리즘 (Dijkstra) (0) | 2017.10.17 |