Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 백준 17822
- 자료구조
- 백준 1406
- 해시구현
- 게리멘더링2
- 버킷 정렬
- 원판 돌리기
- Stack 이란
- 백준 5397
- 별 찍기 10
- 구현
- 해시 구현
- 5397
- 시간 복잡도
- ㅣ풀이
- 백준 1158
- AVL 시간 복잡도
- qorwns
- 백준
- 1764
- 풀이
- heap
- 백준 17471
- 조세퍼스 순열
- 스택의 특징
- 백준 2447
- C/C++ 구현
- c#
- 백준 17779
- dfs
Archives
- Today
- Total
홍시홍의 프로그래밍
[알고리즘] 벨만포드 (특징, 시간복잡도, 구현 방법) 본문
특징
1. 음의 가중치를 갖는 그래프에서 최단경로를 구할 수 있다.
2. 음의 가중치 여부를 알 수 있다
구현 방법
모든 노드의 숫자만큼 거리가 업데이트 될 수 있는가 검사한다
V만큼 E가 업데이트 될 수 있는지 검사한다
그리고 마지막 V+1번 검사할때, 거리가 업데이트된다면 음의 가중치를 갖는 그래프이다
시간 복잡도
V만큼 E가 업데이트 될 수 있는지 검사하므로
O(VE)이다
'알고리즘' 카테고리의 다른 글
| [알고리즘] dfs(깊이 우선 탐색, 시간 복잡도, 사용하는 곳, 특징, 구현방법) (0) | 2020.08.31 |
|---|---|
| [알고리즘] 플로이드 워셜(시간 복잡도, 사용하는 곳, 특징, 구현방법) (0) | 2020.06.11 |
| [알고리즘] 프림 알고리즘(시간 복잡도, 구현방법, 특징) (0) | 2020.06.11 |
| 코사라주 알고리즘(시간복잡도, 구현 방법, 준비 사항) (0) | 2020.06.10 |
| 위상 정렬(사용하는 이유, 특징, 구현, 시간 복잡도) (0) | 2020.06.10 |
Comments