소개글
가중치방향 그래프에서 최단경로를 구합니다.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
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
참고 자료
없음프로그램소스 연관자료
이 자료와 함께 구매한 자료
- URL을 입력받아 다운로드하는 프로그램 4페이지
- 가상디스크에서 파일의 레코드 관리기 19페이지
- 심볼테이블 및 범용 리스트를 이용한 다항식 계산기 프로그램 소스 10페이지
- 배열을 이용한 다항식 계산기 8페이지
- [C언어] 달력출력 프로그램 12페이지