벨만포드는 다익스트라보다 느리고, 비슷하다.
다익스트라랑 다른 점은 음수가중치가 존재해도 사용이 가능하다는 것이다.
그런데 다익스트라보다 시간복잡도가 O(VE)로 크다. 다익스트라는 O(ElgV)
| 2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번) (0) | 2017.10.20 |
|---|---|
| BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선) (0) | 2017.10.19 |
| BOJ 14852 타일채우기 3 풀이 (0) | 2017.10.18 |
| BOJ 2309 일곱난쟁이 풀이 (0) | 2017.10.18 |
| BOJ 2065 줄 세우기 (0) | 2017.10.18 |
다익스트라에 이어서 플로이드 워셜 알고리즘을 공부했다.
다익스트라를 모든 정점에서 돌리면 플로이드 워셜이 된다.
그런데 다익스트라는 음수 가중치를 가지는 간선이 있으면 안된다 한다.
플로이드 워셜은 모든 정점을 돌아보기 때문에 시간복잡도가 O(V^3)이다.
입력에서 중복값 확인을 해주니 정답이 됐다.
위키백과에 JAVA코드도 추가했다.
| 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 |
나무위키에 올라온 사진들을 보며 코드를 작성했다.
MAX값을 2147483647 즉 signed int 의 MAX로 하다보니, 출력에서 꼬여가지고 출력초과과 떴었다.
백준의 출력 용량은 최대 1 MB이다
그 다음에 MAX값을 변경해서 제출하니 시간초과가 뜨는 것이다.
우선순위 큐로 작업하지않고, 리스트에 다 담아서 작업했었음.
그래서 큐에서 값이 변경될 경우에 offer해줬고, 성공했다.
| BOJ 14852 타일채우기 3 풀이 (0) | 2017.10.18 |
|---|---|
| BOJ 2309 일곱난쟁이 풀이 (0) | 2017.10.18 |
| BOJ 2065 줄 세우기 (0) | 2017.10.18 |
| BOJ 11404 플로이드 Floyd-Warshall (0) | 2017.10.18 |
| BOJ 1717 집합의 표현 disjoint-set (0) | 2017.10.17 |