목록2025/02/26 (1)

데이터 분석 기술 블로그

벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘"가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로, 음의 가중치(음수 간선)도 처리 가능하다!"다익스트라와 달리 음수 가중치가 있는 그래프에서도 사용 가능모든 간선을 최대 V-1번 반복하여 최단 경로를 업데이트하는 방식음수 사이클(무한히 거리가 줄어드는 경우)도 감지 가능벨만-포드 알고리즘 동작 원리모든 노드까지의 최단 거리를 무한(∞)으로 초기화, 단 시작 노드는 0으로 설정그래프의 모든 간선을 V-1번 반복하며 갱신 (V는 노드 개수)V번째 반복에서 값이 갱신되면 음수 사이클이 존재함!# Pseudo CodeFUNCTION BellmanFord(graph, start): 거리 = {모든 노드를 ∞(무한대)로 초기화} 거리[start] = 0 # 시작 노드는 0 ..
데이터 사이언스/알고리즘 2025. 2. 26. 19:38
이전 Prev 1 Next 다음