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

[자료구조] BellmanFord 알고리즘

*종*
최초 등록일
2002.12.20
최종 저작일
2002.12
5페이지/워드파일 MS 워드
가격 1,000원 할인쿠폰받기
다운로드
장바구니

소개글

책참고 해서 직접 작성한 C++ 프로그램입니다...^^ 즐공

목차

1. 문제 내용및 설명
2. 알고리즘
3. 소스설명
4. 결과화면
5. 느낀점

본문내용

1. 문제 내용 및 설명BellmanFord 알고리즘을 이용하여 단일 시발점에서 모든 종착점으로의 최단경로와 최소 가중치를 구하라.
§ 그래프는 인접행렬로 구현한다.
§ 길이 인접 행렬을 입력 받는다.
§ 최단경로와 최소 가중치를 출력한다.
2. 알고리즘
§ 음의 길이 사이클이 존재하지 않을 때 n개의 정점으로된 그래프에서 최대 n-1개의 간선으로 된 임의의 두 정점 사이의 최단 경로는 존재한다.
§ 모든 u에 대해 dist^n-1[u]를 구할 때
(1) 최대 k(k>1)개의 간선을 가질 수 있는 상황에서 v로부터 u까지의 최단 경로가 k-1개 이하의 간선을 갖는다면, dist^k[u]=dist^k-1[u]이다.
(2) 최대 k(k-1)개의 간선을 가질수 있는 상황에서 v로부터 u까지의 최단 경로가 정확히 k개의 간선을 갖는다면, 이 경로는 v에서 어떤 정점 j로의 최단 경로와 간선<j,u>로 구성된다. V에서 j로의 최단경로는 k-1개의 간선을 포함하고 그 길이는 dist^k-1[j]가 된다.여기서 그래프에 있는 간선<I,u>에 속하는 모든 정점 I는 j의 후보가 된다. 최단 경로를 구하는 관점에서 보면, dist^k-1[I]+length[I][u]의 값을 최소화시키는 I가 j로 되어야 한다.
§ dist를 다음과 같은 반복식으로 표현한다.

참고 자료

C++ 자료구조론

자료후기(1)

*종*
판매자 유형Bronze개인

주의사항

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

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

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

  • 한글파일 [공학]bellmanford, 자료구조알고리즘 프로그래밍 보고서 4페이지
    그리고 실제 알고리즘이 동작하는 부분에서 모든 vertex를 접근하는 부분은 ... 사실 이 부분은 크게 상관은 없지만 알고리즘대로 구현하기 위해서 그렇게 했다 ... +)// 실행중에 내용이 바뀌기 때문에 temp[j]=g[j].d;// 알고리즘대로
최근 본 자료더보기
탑툰 이벤트
[자료구조] BellmanFord 알고리즘
  • 레이어 팝업
AI 챗봇
2024년 05월 27일 월요일
AI 챗봇
안녕하세요. 해피캠퍼스 AI 챗봇입니다. 무엇이 궁금하신가요?
7:28 오후
New

24시간 응대가능한
AI 챗봇이 런칭되었습니다. 닫기