최단경로문제 동적계획(Floyd 알고리즘) 과Greedy설계법(Dijkstra알고리즘)소스실행후 비교평가

소개글

최단경로문제 동적계획(Floyd 알고리즘) 과Greedy설계법(Dijkstra알고리즘)소스실행후 비교평가에 대한 보고서 자료입니다.

목차

1. 동적계획법(Floyd 알고리즘) 소스 및 결과

2. Greedy 설계법(Dijkstra 알고리즘) 소스 및 결과

3. 두 알고리즘 비교/평가 (시간복잡도)

본문내용

i<=n; i++)
cout << setw(4) << touch[i];
//③ v1에서 vi로가는 최단경로 길이 : leng[i]
cout << "\n" << "③ v1에서 vi로가는 최단경로 길이 : leng[i]" << endl;
for(i=1; i<=n; i++)
cout << setw(4) << leng[i];
//④ 정점1에서 모든정점(2,3,..,n)까지의 최단 경로및 최단거리
cout << "\n" << "④ 정점1에서 모든정점(2,3,..,n)까지의 최단 경로및 최단거리 " << endl;
for(int j=1; j<=n; j++)
{
cout << "v1 -> " << "v" << j << " : ";
path(j);
cout << " v" << j; //자기자신 정점
cout << " (최단거리:" << leng[j] << ")" << endl; //최단거리
}
}
// ▶ 파일로부터 그래프 인접행렬 읽어서 배열W에 저장
int fileopen(int W[MAX][MAX])
{
int n;
//파일로부터 데이터를 읽기위해 ifstream클래스 객체readFile 생성
ifstream readFile("grape.dat",ios::in);
if (!readFile)
{//에러 처리
cerr << "파일을 열수 없습니다." << endl;
exit(1);
}
readFile >> n; //정점 갯수
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
readFile >> W[i][j];
readFile.close(); //파일 닫기
return n; //vertex 갯수 return
}
void dijkstra(int n, int W[MAX][MAX], edge *F) //구조체배열
{
int i, min, vnear; //vnear: 가장가까운 점
int length[MAX]; //최단 경로 길이 임시저장
edge e; //이음선
//선택된 간선 집합 F초기화
for(i=1; i<=MAX; i++)
{
F[i].start_v=0; //이음선의 시작점
F[i].end_v=0; //이음선의 끝점
}
for(i=2 ; i<=n; i++)
{ //v1에서 다른 모든 정점으로 가는 경로가 존재한다고 가정
touch[i] = 1; //v1에서 출발하는 현재 최단경로의
length[i] = W[1][i]; //마지막 정점을 v1로 초기화
leng[i] = W[1][i]; //최단 경로 길이(path함수에서 사용)
}
for(int k=1; k {
min=XX; //XX=무한대 값(999)
for(i=2; i<=n; i++)
if (0<=length[i] && length[i] {
min=length[i];
vnear=i; //가장가까운 점
}
e.start_v = touch[vnear];
e.end_v = vnear;
F[k]=e; //이음선 e를 이음선의 집합 F에 추가
for(i=2; i<=n; i++)
if(length[vnear] + W[vnear][i] < length[i])
{
//Y에 속하지 않는 정점에 대해 최단경로 바꾼다.
length[i] = length[vnear] + W[vnear][i]; //임시//path()출력함수에서 사용(최단경로길이 저장)
leng[i] = length[vnear] + W[vnear][i];
touch[i] = vnear;
}
length[vnear] = -1; //vnear 가 인덱스인 정점을 Y에 추가
}
}
//최단경로 출력
void path(int r)
{
if(touch[r] !=0)
{
path(touch[r]);
cout << " v" << touch[r];
}
}
▶테스트1 (파일명: graph.dat)
▶실행결과1
=>설명
③번의 최단경로 거리( 0 5 4 2 1 )와 ④번의 각 정점에 대한 (최단거리: x)를 비교해보면 같음을 알수 있다.(프로그램이 제대로 구현되었음을 의미)
Floyd 알고리즘의 테스트1과도 결과가 같음을 알 수 있다.
▶테스트2 (파일명:dijkstra2.dat)
▶실행결과2
=>설명
③번의 최단경로 거리( 0 6 7 3 7 9 )와 ④번의 각 정점에 대한 (최단거리: x)를 비교해보면 같은을 알수 있다.(프로그램이 제대로 구현되었음을 의미)
3. Floyd 알고리즘(동적계획법)과 Dijkstra 알고리즘(Greedy설계법) 비교
Floyd 알고리즘도 Dijkstra 알고리즘처럼 최단거리를 구하는 알고리즘이다. 다른 점은 Dijkstra 알고리즘이 한 점에서 출발해서 각 정점에 최단거리를 구하지만, Fload 알고리즘은 모든 점점에서 출발해서 출발 한 정점을 제외한 모든 정점을 도착점으로 하는 최단거리를 구하는 알고리즘이다.
▶모든 경우 시간복잡도
Floyd알고리즘
Dijkstra 알고리즘
관심있는 특정 정점으로부터 다른 모든 정점으로 가는 최단 경로를 알고 싶다면 Floyd알고리즘은 과다하다. Dijkstra알고리즘을 이용하는 것이 더 효율적이다.
① Floyd 알고리즘
- 단위연산 : 세번 중첩된 for 루프안의 지정문
P[i][j]=k or D[i][j]=D[i][k]+D[k][j]
- 입력크기 : n(그래프에서 정점의 개수)
for 루프가 세번 중첩 되었다.
② Dijkstra 알고리즘
- 단위연산 : for 루프안에 2개의 for루프가 있으며, 각각 n-1회 반복한다.
그 안의 명령문 들을 단위연산으로 한다.
첫 번째 for 루프 : min = length[i]
or vnear = i
두 번째 for 루프 : length[i]=length[vnear]+w[vnear][i]
or touch[i] = vnear
- 입력크기 : n(그래프에서 정점의 개수)
바깥 for 루프가 n-1회반복되고, for루프안에 2개의 for 루프가 각각 (n-1)회 반복된다.
시간 복잡도만으로는 플로이드 알고리즘이 대체적으로 느릴 것 같으나, Dijkstra 알고리즘이 한번의 루프를 돌 때마다 하는 일이 많다보니(복잡하다보니) 실제로는 플로이드가 빠른 경우가 상당히 많다.

키워드

최단경로,   동적계획,   플로이드(Floyd)알고리즘,   Greed설계,   다익스트라(Dijkstra)알고리즘