연구문헌
교육정보
심화정보
포커스iN
연구자료
- 문자 DB
- 용어사전
알림마당
CSERIC 광장

단어	벨만-포드 알고리즘
단어	Bellman-Ford algorithm
설명	(몇몇 연결선의 무게는 음인) 무게가 메겨진 그래프에서 단일 소스 최단 경로를 계산한다. Dijkstra의 알고리즘(Dijkstra’s algorithm)은 더 낮은 수행 시간으로 같은 문제를 이루었지만, 연결선의 무게가 양수여야만 한다. 그러므로, 벨만-포드는 보통 음의 연결선 무게가 있을 때만 사용된다. 벨만 포드는 V와 E가 꼭지점과 연결선의 수라고 할 때 O(VE)의 시간에 수행된다. 벨만-포드 알고리즘의 분산된 변형은 라우팅 정보 프로토콜(Routing Information Protocol; RIP)에서 사용된다.