최단거리 검색탐색-다익스트라

목차

1. 문제 제기

2. 문제 분석

3. 문제 해결

4. 결과 화면

5. 느낀점

본문내용

f(tail < i && head < i && waste > 0)// 예외처리
break;
cout << "잘못된값을입력했습니다" << endl;
}
h.matrix[tail][head] = waste;// 행렬에저장
do{// 노드의저장여부를물어봄
cout << "더저장하시겠습니까? (y/n) : ";
cin >> more;
}while(more != 'y' && more != 'Y' && more != 'n' && more != 'N');
}while(more == 'y' || more == 'Y');// Y라답했을때
return is;
}
// 최단경로찾기함수
void path::ShortPath()
{
int a,b,i,j,temp=0,k;
bool first = true;
head = new Node[size];// 최단경로와비용을저장할노드를크기만큼공간할당
for(i=0 ; i {
head[i].Gpath = new int[size];
head[i].waste = -1;
}
high = 0;// 스택높이의초기화
cout << "최단거리를구할v를입력해주세요(0-" << size-1 << ") : ";
cin >> a;
store = new int[size];// 최단거리집단의인접정점을저장할스택의공간할당
head[a].waste = 0;// 시작정점의초기화
head[a].Gpath[0] = a;// 시작정점의초기화
head[a].GH = 0;// 시작정점의초기화
for(i=0 ; i if(first && matrix[a][i] !=0){// 만약이어져있고처음일때
first = false;// 첫저장을했다는변수설정
temp = i;// 현재선두권저장
}
else if(matrix[a][i] < matrix[a][temp] && !first && matrix[a][i] !=0){
// 만약이어져있고기존값보다적을때
store[high] = temp;// 예전선두권을스택에저장
high++;// 스택높이올려주기
temp = i;// 현재선두권저장
}
else if(!first && matrix[a][i] !=0)// 만약이어져있고기존값보다작을때
{
store[high] = i;// 패배자를스택에저장
high++;// 스택높이올려주기
}
}
for(i=0 ; i if(matrix[temp][i] != 0 && i != a){
store[high] = i;
high++;
}
}
head[temp].waste = matrix[a][temp];// 첫번째연산의저장
head[temp].Gpath[0] = a;// 첫번째연산의저장
head[temp].Gpath[1] = temp;// 첫번째연산의저장
head[temp].GH = 1;// 첫번째연산의저장
while(high != 0){
high--;// 스택에서맨위에꺼를pop
b = store[high];// 지금까지최소경로에인접해있는한정점을꺼내옴
first = true;// 처음저장할때변수초기화
for(i=0 ; i {
// 만약연결이있고, 이미최소경로안에있지않은정점일때
if(matrix[i][b] != 0 && head[i].waste != -1)
{
if(first){// 처음저장일때
head[b].waste = head[i].waste + matrix[i][b];
// 비용저장
temp = i;// 선두권으로등극
first = false;
}
// 처음저장이아니고, 1등이바뀔때
else if(head[b].waste > head[i].waste + matrix[i][b])
{
// 비용을바꿔서저장
head[b].waste = head[i].waste + matrix[i][b];
temp = i;// 선두권으로등극
}
}
}
// 선택된정점의경로에최소경로의정점중최소의비용을가진정점의경로를복사
for(i=0; i <= head[temp].GH ; i++)
{
head[b].Gpath[i] = head[temp].Gpath[i];
}
// 경로의크기를한칸키워주고
head[b].GH = head[temp].GH +1;
head[b].Gpath[head[b].GH] = b;// 경로의마지막에자신을저장
k=high;
// 꺼낸정점의인접한정점들을스택에넣는과정
for(i=0 ; i {
for(j=0 ; j<=k ; j++)
{
if(head[i].waste == -1 && matrix[b][i] != 0
&& store[j] != i)
{
store[high] = i;
high++;
}
}
}
}
}
// 출력함수
ostream &operator <<(ostream &is,path &h)
{
int i,j;
cout << "최단경로는다음과같습니다" << endl;
for(i=0 ; i {
cout << i << "까지의경로는: ";
if(h.head[i].waste == -1)// 연결이안되있는경우
cout << "∞" << endl;
else{// 연결이되있는경우
cout << h.head[i].Gpath[0];
for(j=1 ; j <= h.head[i].GH ; j++)
cout << " -> " << h.head[i].Gpath[j];
cout << endl << " 총비용: " << h.head[i].waste << endl;
}
}
return is;
}
4. 결과 화면
5. 느낀점
데이터구조 수업이 끝나갑니다. 아쉬운것도 어려운 것도 많았지만, 잘 따라가려고 노력한 만큼 정신없이 지나간 것만 같습니다. 아직도 제 실력은 많이 부족하지만 언제나 잘 설명해서 알려주셔서 감사합니다. 그래프도 결국 배열과 링크드로 만들어낸 하나의 개념에 불과하다는 것을 이제야 조금씩 깨달아갑니다. 처음에 배울때는 트리나 그래프도 그 형상을 생각하게 되어 저런 것들을 만들어야하는구나 하고 어렵다고 생각했는데, 그 이미지들은 그냥 개념을 설명하기 위한 방법일 뿐이지 결국 소스에서 만드는 과정은 개념만 새로울 뿐 같은 재료를 가지고 프로그래밍을 한다는 것을 깨달았습니다.

키워드

다익스트라,   자료구조,   알고리즘,   하노이