익명 사용자
로그인하지 않음
토론
기여
계정 만들기
로그인
IT 위키
검색
벨만-포드 알고리즘
편집하기
IT 위키
이름공간
문서
토론
더 보기
더 보기
문서 행위
읽기
편집
원본 편집
역사
경고:
로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다.
로그인
하거나
계정을 생성하면
편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
스팸 방지 검사입니다. 이것을 입력하지
마세요
!
고급
특수 문자
도움말
문단 제목
2단계
3단계
4단계
5단계
형식
넣기
라틴 문자
확장 라틴 문자
IPA 문자
기호
그리스 문자
그리스어 확장
키릴 문자
아랍 문자
아랍어 확장
히브리 문자
뱅골어
타밀어
텔루구어 문자
싱할라 문자
데바나가리어
구자라트 문자
태국어
라오어
크메르어
캐나다 원주민 언어
룬 문자
Á
á
À
à
Â
â
Ä
ä
Ã
ã
Ǎ
ǎ
Ā
ā
Ă
ă
Ą
ą
Å
å
Ć
ć
Ĉ
ĉ
Ç
ç
Č
č
Ċ
ċ
Đ
đ
Ď
ď
É
é
È
è
Ê
ê
Ë
ë
Ě
ě
Ē
ē
Ĕ
ĕ
Ė
ė
Ę
ę
Ĝ
ĝ
Ģ
ģ
Ğ
ğ
Ġ
ġ
Ĥ
ĥ
Ħ
ħ
Í
í
Ì
ì
Î
î
Ï
ï
Ĩ
ĩ
Ǐ
ǐ
Ī
ī
Ĭ
ĭ
İ
ı
Į
į
Ĵ
ĵ
Ķ
ķ
Ĺ
ĺ
Ļ
ļ
Ľ
ľ
Ł
ł
Ń
ń
Ñ
ñ
Ņ
ņ
Ň
ň
Ó
ó
Ò
ò
Ô
ô
Ö
ö
Õ
õ
Ǒ
ǒ
Ō
ō
Ŏ
ŏ
Ǫ
ǫ
Ő
ő
Ŕ
ŕ
Ŗ
ŗ
Ř
ř
Ś
ś
Ŝ
ŝ
Ş
ş
Š
š
Ș
ș
Ț
ț
Ť
ť
Ú
ú
Ù
ù
Û
û
Ü
ü
Ũ
ũ
Ů
ů
Ǔ
ǔ
Ū
ū
ǖ
ǘ
ǚ
ǜ
Ŭ
ŭ
Ų
ų
Ű
ű
Ŵ
ŵ
Ý
ý
Ŷ
ŷ
Ÿ
ÿ
Ȳ
ȳ
Ź
ź
Ž
ž
Ż
ż
Æ
æ
Ǣ
ǣ
Ø
ø
Œ
œ
ß
Ð
ð
Þ
þ
Ə
ə
서식 지정
링크
문단 제목
목록
파일
각주
토론
설명
입력하는 내용
문서에 나오는 결과
기울임꼴
''기울인 글씨''
기울인 글씨
굵게
'''굵은 글씨'''
굵은 글씨
굵고 기울인 글씨
'''''굵고 기울인 글씨'''''
굵고 기울인 글씨
벨만-포드 알고리즘(Bellman-Ford algorithm, 벨만-포드 算法)은 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로, 음의 가중치를 가진 간선이 존재하는 경우에도 사용할 수 있다. ==개요== 벨만-포드 알고리즘은 리처드 벨만(Richard Bellman)과 레스터 포드(Lester Ford)에 의해 제안된 알고리즘으로, 다익스트라 알고리즘과는 달리 음의 가중치를 허용한다. 이 알고리즘은 동적 계획법에 기반하여 최단 경로를 반복적으로 개선하며, 음의 사이클(negative cycle)의 존재 여부도 탐지할 수 있는 특징이 있다. ==동작 원리== 그래프 G = (V, E)와 시작 정점 s가 주어졌을 때, 다음과 같은 방식으로 알고리즘이 진행된다. *모든 정점 v ∈ V에 대해 거리 d[v]를 ∞로 초기화하고, d[s] = 0으로 설정한다. *간선 (u, v) ∈ E에 대해 d[v] > d[u] + w(u, v)인 경우, d[v] ← d[u] + w(u, v)로 업데이트한다. *위의 간선 완화를 총 V-1회 반복한다. *이후 모든 간선을 한 번 더 검사하여, 여전히 d[v] > d[u] + w(u, v)인 간선이 존재하면 음의 사이클이 존재하는 것이다. ==알고리즘 복잡도== 벨만-포드 알고리즘의 시간 복잡도는 O(VE)이다. 이는 모든 간선을 최대 V-1회 순회하기 때문이다. 따라서 정점 수가 많고 간선이 많은 밀집 그래프에서는 성능이 저하될 수 있다. == 예시== 다음은 음의 가중치 간선을 포함하는 예제 그래프와 벨만-포드 알고리즘 수행 과정을 나타낸 것이다. 그래프 구조: [[파일:음의 간선이 있는 그래프.png|700x700픽셀]] 간선 목록: 아래 순서대로 순회한다. 벨만-포드는 순서에 따라 알고리즘의 중간 전개가 달라질 수 있다. * A → B (6) *A → C (7) *B → C (8) *B → D (5) *B → E (-4) *C → D (-3) *C → E (9) *D → B (-2) *E → D (7) 시작 정점: A 거리 테이블 (d[i]는 정점 i까지의 최단 거리): {| class="wikitable" !반복 단계||A||B||C||D||E |- |초기값||0||∞||∞||∞||∞ |- |1회 반복 |0||2|| 7||4||2 |- |2회 반복 ||0 ||2||7||4|| −2 |- |3회 반복 || 0 || 2||7|| 4||−2 |- |4회 반복 ||0 ||2||7||4||−2 |} '''1회 반복 – 간선별 처리''' # A → B (6): A = 0이므로 B = 0 + 6 = 6 → B 갱신 # A → C (7): A = 0이므로 C = 0 + 7 = 7 → C 갱신 # B → C (8): B = 6이므로 C = 6 + 8 = 14 → 기존 C = 7이므로 변화 없음 # B → D (5): B = 6이므로 D = 6 + 5 = 11 → D 갱신 # B → E (−4): B = 6이므로 E = 6 − 4 = 2 → E 갱신 # C → D (−3): C = 7이므로 D = 7 − 3 = 4 → D 갱신 (기존 11 → 4) # C → E (9): C = 7이므로 E = 7 + 9 = 16 → 기존 E = 2이므로 변화 없음 # D → B (−2): D = 4이므로 B = 4 − 2 = 2 → B 갱신 (기존 6 → 2) # E → D (7): E = 2이므로 D = 2 + 7 = 9 → 기존 D = 4이므로 변화 없음 '''2회 반복 – 간선별 처리''' # A → B (6): A = 0이므로 B = 0 + 6 = 6 → 기존 B = 2이므로 변화 없음 # A → C (7): A = 0이므로 C = 0 + 7 = 7 → 기존 C = 7이므로 변화 없음 # B → C (8): B = 2이므로 C = 2 + 8 = 10 → 기존 C = 7이므로 변화 없음 # B → D (5): B = 2이므로 D = 2 + 5 = 7 → 기존 D = 4이므로 변화 없음 # B → E (−4): B = 2이므로 E = 2 − 4 = −2 → E 갱신 (기존 2 → −2) # C → D (−3): C = 7이므로 D = 7 − 3 = 4 → 기존 D = 4이므로 변화 없음 # C → E (9): C = 7이므로 E = 7 + 9 = 16 → 기존 E = −2이므로 변화 없음 # D → B (−2): D = 4이므로 B = 4 − 2 = 2 → 기존 B = 2이므로 변화 없음 # E → D (7): E = −2이므로 D = −2 + 7 = 5 → 기존 D = 4이므로 변화 없음 '''3회 반복 & 4회 반복''' *모든 간선 검사 시 더 이상 갱신 없음 (거리 안정화됨) *정점이 5개이므로 5 - 1 = 4회 까지만 반복된다. ==구현== <syntaxhighlight lang="python"> def bellman_ford(graph, start): distance = {v: float('inf') for v in graph} distance[start] = 0 for _ in range(len(graph) - 1): for u in graph: for v, w in graph[u]: if distance[u] + w < distance[v]: distance[v] = distance[u] + w for u in graph: for v, w in graph[u]: if distance[u] + w < distance[v]: raise ValueError("음의 사이클이 존재합니다.") return distance </syntaxhighlight> ==장단점== '''장점''' *음의 가중치 허용 *음의 사이클 탐지 가능 * 간단한 구현 '''단점''' * 시간 복잡도가 O(VE)로 느림 *밀집 그래프에서는 비효율적 *음의 사이클 존재 시 경로 무의미 ==같이 보기 == *[[다익스트라 알고리즘]] *[[플로이드-워셜 알고리즘]] *[[최단 경로 알고리즘]] *[[그래프 이론]] *[[동적 계획법]] ==참고 문헌 == *Bellman, R. (1958). On a routing problem. ''Quarterly of Applied Mathematics'', 16(1), 87–90. *Ford, L. R. (1956). Network flow theory. ''RAND Corporation Report'' P-923. ==각주== [[분류:알고리즘]] [[분류:그래프 이론]]
요약:
IT 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는
IT 위키:저작권
문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다.
저작권이 있는 내용을 허가 없이 저장하지 마세요!
취소
편집 도움말
(새 창에서 열림)
둘러보기
둘러보기
대문
최근 바뀜
광고
위키 도구
위키 도구
특수 문서 목록
문서 도구
문서 도구
사용자 문서 도구
더 보기
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
문서 기록