• 파일시티 이벤트
  • LF몰 이벤트
  • 서울좀비 이벤트
  • 탑툰 이벤트
  • 닥터피엘 이벤트
  • 아이템베이 이벤트
  • 아이템매니아 이벤트
  • 위잇 도시락 이벤트

[알고리즘]최단경로탐색-벨만포드(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

참고 자료

쉽게 배우는 알고리즘 - 문병로저
*준*
판매자 유형Bronze개인인증

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우
최근 본 자료더보기
탑툰 이벤트
  [알고리즘]최단경로탐색-벨만포드(bellman-ford)알고리즘
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업