[자료구조] BellmanFord 알고리즘

등록일 2002.12.20 MS 워드 (doc) | 5페이지 | 가격 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++ 자료구조론
*원하는 자료를 검색 해 보세요.
  • [C++ 프로젝트] 학생 관리 프로그램입니다. 20페이지
    #include #include "StdInfor.h" #include "StdManagerment.h" using namespace std; StdInfor *student[20];//StdInfor 클래스로..
  • C++ 기초플러스 2장 프로그래밍 연습 4페이지
    2.거리에 대해 마일 단위로 입력을 요구하고, 그것을 킬로미터 단위로 환산하는 프로그램을 작성하시오 (1 마일은 1.60934 킬로미터이다.) #include <iostream> double street(int n); ..
  • C++ 배열 입력 및 출력 0페이지
  • [서평] C++ 프로그래밍 3페이지
    프로그래밍 언어가 8백종이 넘는다고 한다. 그 중에 ‘자바’가 선두권이고 (특히 한국은) 향후에도 그럴 거라고 하지만 ‘오라클’의 욕심이 미래를 망칠 거라는 우려도 있다. ‘스티브 잡스’는 생전 4인치 이하의 스마트폰에 강박하..
  • [서평] C++ 프로그래밍 워크북 3페이지
    여러 번 반복되는 문제는 그만큼 중요하다는 뜻이리라. 개념 이해를 암기하기 위한 반복이다. 문제 풀이는 이해를 위해서 하는 것이지 평가를 위해 하는 것이 아니다. 이런 관점에서 대부분의 교과서에는 문제가 제공된다. 이 책처럼 ..
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [자료구조] BellmanFord 알고리즘