[알고리즘] Dijkstra 알고리즘 프로그래밍

소개글

[알고리즘] Dijkstra 알고리즘 프로그래밍에 대한 보고서 자료입니다.

목차

Ⅰ. Overview
◎ 문제
◎ Dijkstra 알고리즘란
◎ input 값
◎ output 값

Ⅱ. Algorithms used
◎ 주요 배열 및 선언된 변수
◎ 프로그램 알고리즘

Ⅲ. Capability and Limitations

Ⅳ. How To Run

Ⅴ.CODE

본문내용

정점으로 잡고 시작하였기 때문에 동적인 면을 고려하지 못하 였다.
정점을 추가하여 그래프를 삽입하였을 경우 불안한 경우를 발견하였다.
또한 위에서도 언급하였듯이 다익스트라 알고리즘의 경우 호의 길이가 음인 경우에는
이 알고리즘을 쓸 수가 없다.
이 경우에는 Bellman-Ford 알고리즘을 이용할 수있다
Ⅳ. How To Run
Ⅰ.주어진 directed graph
ⅰ-1.input : 시작점을 v0으로 주었을 경우
ⅰ-2. output
ⅱ-1. input : 시작점을 v1으로 주었을 경우
ⅱ-2, output
ⅲ-1.input : 시작점을 v2로 주었을 경우
ⅲ-2. output
ⅳ-1. input : 시작점을 v3로 주었을 경우
ⅳ-2. input
ⅴ-1. input : 시작점을 v4로 주었을 경우
ⅴ-2. output
Ⅱ.주어진 directed graph
ⅰ-1. input : 시작점을 v0로 주었을 경우
ⅰ-2. output
Ⅲ.주어진 directed graph
ⅰ-1. input : 시작점을 v4로 주었을 경우
ⅰ-2. output
Ⅴ.CODE
#include
#include
#define x 100000
void short_path();
int touch[5]; //최단거리상에서 현 노드의 바로 전 노드 index
int length[5]; //touch에서 현노드까지의 최단거리
int F[5][5];
int y[5] = {-1,-1,-1,-1,-1}; //최단거리 경로상에 놓여있는 이음선의 집합
int weight[5] ={-1,-1,-1,-1,-1}; //가중치
int y_index=0;
int f_index=0;
int f_num=0;
int max_f_num=2;
int i,j=0;
int linked_pointer;
int y1=0;
int vnear=0;
int w[5][5]={
{x,7,4,6,1},
{x,x,x,x,x},
{x,2,x,5,x},
{x,3,x,x,x},
{x,x,x,1,x}};
void main(){
for(int z=0 ; z<5 ; z++) //F배열 초기화
{
for(int y=0 ; y<5 ; y++)
{
F[z][y] = -1;
}
}
printf("시작하고자 하는 정점을 선택하시오(0,1,2,3,4): ");
scanf("%d",&y1);
printf("\n");
if((0>y1) || (y1>=5))
{
printf("정의되지 않은 정점입니다. 다시선택하십시오. \n");
exit(0);
}
else
short_path();
}
void short_path()
{
y[y_index] = y1;
F[f_index][f_num] = y1;
//최단거리 table의 초기화
for(int a=0 ; a<5 ; a++)
{
if(a != y1)
{
touch[a] = y1;
length[a] = w[y1][a];
}
else
{
touch[a] = y1;
length[a] = x;
}
}
for(int repeat=0 ; repeat < 4 ; repeat++)
{
int min = x;
for(int b=0 ; b<5 ; b++)
{
if(length[b] < min)
{
min = length[b];
vnear = b;
linked_pointer = touch[b];
}
}
if(min == x) //더이상 갈수있는 노드가 없을 경우
break;
if(vnear != y[y_index]) //시작한 정점이 모든 정점을 가지 못할 경우를 고려
y[++y_index]=vnear;
weight[vnear] = min;
if(y1 == linked_pointer)
{
if(f_index == 0) //첫번째 최단거리 경로일경우 위에서 초기화 해주었기때문
F[f_index++][++f_num] = vnear;
else
{
f_num=0;
F[f_index][f_num++] = linked_pointer;
F[f_index][f_num] = vnear;
}
}
else
{
for(i=0 ; i<=f_index ; i++)
{
for(j=0;j<=max_f_num;j++)
{
if(F[i][j] == linked_pointer)
{
F[i][++j]=vnear;
max_f_num++;
break;
}
}
}
}
for(int c=0 ; c < 5 ; c++)
{
if((length[vnear] + w[vnear][c] < length[c]) && (length[c] != x))
{
length[c] = length[vnear] + w[vnear][c];
touch[c] = vnear;
}
}
length[vnear] = x;
}
//다른 정점으로 갈수 있는 노드가 없을 경우
if((f_index == 0) && (max_f_num == 2))
printf("다른 정점으로 이동할 노드가 존재하지 않습니다.\n");
else
{
printf("<<최단거리상에 놓여있는 이음선의 집합>>\n Y{");
for(int d=0 ; d < 5 ; d++)
{
if(y[d] != -1)
{
if(d < y_index)
printf("%d,",y[d]);
else
printf("%d",y[d]);
}
}
printf("}\n\n");
printf("<<시작점 : %d>>\n",y1);
printf("<시작점에서 각 정점마다의 최단거리 PATH>\n");
for(int g=0 ; g <= f_index ; g++)
{
for(int h=0 ; h <= max_f_num ; h++)
{
if (h != 0)
{
if(F[g][h] != -1)
{
for(int k=0; k<=h ;k++)
{
if(k != h)
printf("%d -> ",F[g][k]);
else
printf("%d",F[g][k]);
}
printf("\n");
}
}
}
}
printf("<시작점에서 각 정점까지의 최단거리를 잇는 이음선가중치의 합> \n");
for(int k=0; k<5 ; k++)
{
if(weight[k] != -1)
{
printf("%d -> %d : %d\n",y1,k,weight[k]);
}
}
}
}

키워드

다익스트라,   Dijkstra,   최단거리,   알고리즘,   프로그래밍