검색어 입력폼
평가점수B

그래프에서 최단경로구하기

저작시기 2006.11 |등록일 2006.12.17 파일확장자압축파일 (zip) | 8페이지 | 가격 1,200원

소개글

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

컴파일 실행환경

C++

본문내용

Ⅰ. BellmanFord 알고리즘을 이용한 한 정점에서 모든 정점으로의 최단경로 구하기

1. BellmanFord 알고리즘
한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘으로 BellmanFord 알고리즘이 있다. 이는 Dijkstra 알고리즘에 의하는 경우 가중치가 음수인 경로가 있을 때 최단경로를 올바르게 구할 수 없던 오류를 수정한 알고리즘으로서, 선행하는 간선수를 늘려가면서 해당하는 정점으로의 비용을 계속해서 구해나가는 것이다. 이 알고리즘에 의하여 경로를 구하려면 선행하는 간선수를 알아야 하며, 이전에 해당 정점까지의 비용을 계산한 결과를 알아야한다. BellmanFord 알고리즘을 간단히 나타내면 아래와 같다.

for(int i=0; i<n; I++) dist[i] = length[v][i];
for(int k=2; k<=n-1;k++)
for(u!=v이고 최소한 하나의 진입 간선을 갖는 u에 대해)
for(그래프의 각 <i,v>에 대해)
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을 입력하여 준다.

압축파일내 파일목록

Graph.dsw
Graph.ncb
Graph.plg
Graph.dsp
G1BF.jpg
G2BF.jpg
G2AC.jpg
G1AC.jpg
graph.cpp
Graph.opt
G1.jpg
G2.jpg
최단경로구하기.hwp
Debug/vc60.idb
Debug/vc60.pdb
Debug/Graph.pch
Debug/Graph.exe
Debug/Graph.pdb
Debug/graph.obj
Debug/Graph.ilk
다운로드 맨위로