Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜)
Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜) 벨만-포드 알고리즘(Bellman-ford-moore Algorithm) ● 그래프에서 최단거리를 구하는 알고리즘 ● 음수 가중치 에지가 있어도 수행가능 ● 시간 복잡도 O(VE), 음수 사이클 여부 판단 가능 ● 벨만-포드 구현 방법 1. 에지 중심으로 동작하므로 그래프를 에지 리스트로 표현(tuple로 출발지점, 도착지점, 가중치 삽입) 2. 최단 거리 배열을 초기화(출발 지점은 0으로, 나머지는 무수히 큰 값으로 초기화) 3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(일반적으로 출발 노드), N-1번 에지 사용 횟수를 반복하기 4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트 최단거리 업데이트 ..
Algorithm/알고리즘 공부 일기
2024. 3. 13. 10:50
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 유클리드 호제법
- 에라토스테네스의 체
- 알고리즘
- C++ Stack
- 이분 매칭
- DP
- java
- Do it!
- C++
- 카운팅 정렬
- 자바스크립트
- CSS
- 반복문
- 백준 풀이
- DFS
- 투 포인터
- 알고리즘 공부
- 자료구조
- 자바
- c++ string
- html
- 스프링 부트 crud 게시판 구현
- BFS
- 세그먼트 트리
- 유니온 파인드
- 백준
- HTML5
- 우선순위 큐
- js
- 스택
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함