[알고리즘/이론] 벨만-포드 알고리즘

벨만-포드 알고리즘 벨만-포드 알고리즘은 가중치를 가지는 방향그래프의 최단거리를 구하는 데 사용되는 알고리즘입니다. 특징으로 음의 가중치를 가지는 경우에도 사용할 수 있습니다. 또한 출발점에서 도달가능한 음의 순환의 존재 여부를 확인할 수도 있습니다. 음의 순환이 존재하면 최단거리는 구할 수 없습니다. 모든 최단경로는 순환을 가지지 않으며 따라서 한 정점을 두 번 이상 방문하지 않습니다. 그래프에 정점이 V개 있다면 최단 경로는 최대 V-1개의 간선을 가질 수 있습니다. 최단거리 계산에는 출발점에서 도착점까지의 경로를 순서대로 완화함으로써 최단거리 값을 구할 수 있다는 정리가 이용됩니다. 그래프의 모든 간선을 V-1번 완화(노드의 추정최단거리 값을 갱신하는 행위)하면 한 출발점에서의 모든 다른 노드까지로..
알고리즘/이론 2022. 1. 2. 15:23
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
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 31
글 보관함
반응형
250x250