레포트샵

[자료구조] [C++]그래프에서 최단경로구하기

레포트 > 공학계열 > 자료상세보기 (자료번호:163127)

구매가격
900원 할인쿠폰810원
등록/수정
2007.04.23 / 2007.04.24
파일형식
fileiconzip(압축파일)
페이지수
7페이지
자료평가
평가한 분이 없습니다.
  • 다운로드
  • 장바구니 담기

이전

  • icon

다음

닫기

이전큰이미지 다음큰이미지
  • 최대 100페이지까지 확대보기 서비스를 제공합니다.
신규가입 200원 적립! + 10% 할인쿠폰 3장지급! banner구매자료를 평가하면 현금처럼 3%지급!

하고 싶은 말

가중치방향 그래프에서 최단경로를 구합니다.
BellmanFord 알고리즘을 이용하여 한정점에서 각 정점으로의 최단경로를 구합니다.
구하는 과정도 출력하여 줍니다.
모든쌍의 최단경로를 구하여 줍니다.
구하는 과정도 출력하여 줍니다.

본문내용


Ⅰ. BellmanFord 알고리즘을 이용한 한 정점에서 모든 정점으로의 최단경로 구하기
1. BellmanFord 알고리즘
한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘으로 BellmanFord 알고리즘이 있다. 이는 Dijkstra 알고리즘에 의하는 경우 가중치가 음수인 경로가 있을 때 최단경로를 올바르게 구할 수 없던 오류를 수정한 알고리즘으로서, 선행하는 간선수를 늘려가면서 해당하는 정점으로의 비용을 계속해서 구해나가는 것이다. 이 알고리즘에 의하여 경로를 구하려면 선행하는 간선수를 알아야 하며, 이전에 해당 정점까지의 비용을 계산한 결과를 알아야한다. BellmanFord 알고리즘을 간단히 나타내면 아래와 같다.
for(int i=0; i for(int k=2; k<=n-1;k++)
for(u!=v이고 최소한 하나의 진입 간선을 갖는 u에 대해)
for(그래프의 각 에 대해)
if(dist[u] > dist[i] + length[i][u]) dist[u] = dist[i] + length[i][u];
2. 그래프의 경로 탐색을 위한 클래스 정의
특정 그래프의 최단경로를 탐색하기 위한 연산을 수행하기 위해서 클래스를 정의한다. 클래스에는 그래프를 저장하기 위한 2차원 배열을 선언하고, 각 경로로의 비용을 저장하기 위한 배열 dist를 선언한다. 그래프가 삽입될 배열 GraphArray의 value는 가중치를 나타낸다. 클래스의 정의는 아래와 같다.

class Graph {
private:
int GraphArray[7][7]; // 그래프를 가중치 인접 행렬로 표현.
int dist[7]; // 최단 경로를 구할때 이용할 배열.
public:
Graph();
void InsertCost(int i, int j, int n); // 그래프에 가중치를 삽입하는 함수.
};

InsertCost 함수는 가중치 인접배열에 각 정점간의 가중치를 입력해주는 역할을 한다. 인접배열에서 정점간 경로가 없는 경우는 1000을 입력하여 주고, 자신에 대하여는 0을 입력하여 준다.

태그 bellmanford, allcosts, 최단경로, 최소비용, 벨만포드알고리즘

자료평가

아직 평가한 내용이 없습니다.

오늘 본 자료

  • 오늘 본 자료가 없습니다.
  • img

    저작권 관련 사항 정보 및 게시물 내용의 진실성에 대하여 레포트샵은 보증하지 아니하 며, 해당 정보 및 게시물의 저작권과 기타 법적 책임은 자료 등록자에게 있습니다. 위 정보 및 게시물 내용의 불법적 이용, 무단 전재·배포는 금지됩니다. 저작권침해, 명예훼손 등 분쟁요소 발견시 고객 센터에 신고해 주시기 바랍니다.