Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜)

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜) 벨만-포드 알고리즘(Bellman-ford-moore Algorithm) ● 그래프에서 최단거리를 구하는 알고리즘 ● 음수 가중치 에지가 있어도 수행가능 ● 시간 복잡도 O(VE), 음수 사이클 여부 판단 가능 ● 벨만-포드 구현 방법 1. 에지 중심으로 동작하므로 그래프를 에지 리스트로 표현(tuple로 출발지점, 도착지점, 가중치 삽입) 2. 최단 거리 배열을 초기화(출발 지점은 0으로, 나머지는 무수히 큰 값으로 초기화) 3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(일반적으로 출발 노드), N-1번 에지 사용 횟수를 반복하기 4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트 최단거리 업데이트 ..
Algorithm/알고리즘 공부 일기 2024. 3. 13. 10:50
1
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/11   »
일 월 화 수 목 금 토
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
글 보관함