[알고리즘]최단경로탐색-벨만포드(bellman-ford)알고리즘
- 최초 등록일
- 2011.12.23
- 최종 저작일
- 2011.12
- 11페이지/ 압축파일
- 가격 10,000원
소개글
1.Bellman-Ford 알고리즘 이란?
벨만-포드 알고리즘은 최단 경로를 구하는 알고리즘의 한 종류로 지난 다익스트라 알고리즘 과제에서 했었던 최단경로 찾기와 비슷한 알고리즘이다. 다만 다른점이 있다면 다익스트라 알고리즘에서는 음의 가중치를 허용하지 않았다면 벨만-포드알고리즘에서는 입력 그래프 G=(V,E)에서 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우의 최단경로를 구하는 알고리즘이다. 단 음의 가중치는 허용하지만 가중치 합이 음인 싸이클은 허용하지 않는다. 음의 싸이클이 있다면 해당 싸이클을 몇 번이고 반복해서 돌아 경로의 가중치 합을 무한정 낮출수 있기 때문이다.
2.벨만-포드 알고리즘의 의사코드
벨만-포드 알고리즘은 간선을 최대 1개사용하는 최단경로, 간선을 최대 2개 사용하는 최단경로 이런식으로 최대 n-1개 사용하는 최단경로까지 구해나간다.
코드는 다음과 같다.
BellmanFord(G,r)
{
for each uV
d[u]<-;
d[r]<-0;
❶for i<- 1 to |V|-1
❷for each (u,v)E
if(d[u]+w(u,v)
❸d[v]<-d[u]+w(u,v);
prev[v]<-u;
}
>음의 싸이클 존재 여부 확인
❹ for each (u,v)E
if(d[u]+w(u,v)
}
컴파일 실행환경
Visual Studio 2010
압축파일 내 파일목록
bellman-ford/bellman-ford/bellman-ford.c
bellman-ford/bellman-ford/bellman-ford.vcxproj
bellman-ford/bellman-ford/bellman-ford.vcxproj.filters
bellman-ford/bellman-ford/bellman-ford.vcxproj.user
bellman-ford/bellman-ford/input.txt
bellman-ford/bellman-ford.sln
bellman-ford/bellman-ford.suo
벨만포드알고리즘.hwp
참고 자료
쉽게 배우는 알고리즘 - 문병로저