다익스트라알고리즘

목차

1. 실행 예제

2. 프로그램 소스

본문내용

",&n,&w);
if(w>=99)
{
printf("가중치를 넘었습니다. 다시 입력 하세요.\n");
y--;
continue;
}
graph[x][n]=w;
}
}
}
void matrixprint(int graph[][max],int num)//인접 행렬을 프린트 해줍니다.
{
int x,y;
printf("\n가중치를 간는 인접행렬 \n");
printf(" ");
for(x=0;x {
printf("%3d",x);
}
printf("\n\n");
for(x=0;x {
printf("%d ",x);
for(y=0;y {
if(graph[x][y]==99)//무한대 값이 입력 돼었으면 무한대 표시를
//출력 합니다.
{
printf(" ∞");
continue;
}
printf("%3d",graph[x][y]);
}
printf("\n");
}
}
int dists(int graph[][max],int n,int dist[],int path[])//배열 dist를 구합니다.
{
int i,k,w;
int u,start;
int found[max]={0};
printf("\n시작점을 입력 하세요.");
scanf("%d",&start);
for(i=0; i {
dist[i]=graph[start][i];//dist행렬을 초기화 합니다.
}
printf("\n\n----dist 출력------ -------path출력-----\n");
found[start]=TRUE;//시작 정점은 TRUE 값으로 초기화 합니다.
for(k=0;k {
distprint(dist,n,path);
u=choose(dist,n,found);
found[u]=TRUE;
for(w=0;w {
if(found[w]==0)
{
if(dist[u]+graph[u][w] {
path[w]=u;
dist[w]=dist[u]+graph[u][w];
}
}
}
}
printf("\n");
return start;//시작 정점을 리턴 해줍니다.
}
int choose(int dist[], int n, int found[])//중간 정점으로 선택 되지 않은 정점중 가장 작은 정점을 구합니다.
{
int u=0;
int i;
int min=gmax;
for(i=0;i {
if(found[i]==0)
{
if(min>dist[i])
{
min=dist[i];
u=i;
}
}
}
return u;//dist배열의 첨자 값을 리턴 합니다.
}
void distprint(int dist[], int n,int path[])//path 배열과 dist 배열을 프린트 해 줍니다.
{
int i;
for(i=0;i {
if(dist[i]==99)
{
printf(" ∞");
continue;
}
printf("%3d",dist[i]);
}
printf(" ");
for(i=0;i {
printf("%3d",path[i]);
}
printf("\n");
}
void shortestpath(int path[],int n,int start,int dist[])
{
int i,j,buff;
int stack[max]={0};
int top;
printf("각 정점 까지의 최단 경로 입니다.\n");
for(j=0;j {
top=0;
if(j==start)//시작 정점은 무시하고 넘어 갑니다.
{
continue;
}
else if(dist[j]==gmax)//dist값이 무한대가 나온경우 넘어 갑니다.
{
continue;
}
buff=j;
for(i=0;i {
stack[i]=buff;
top++;
buff=path[buff];
if(buff==0)//path배열에서 0이 나오면 종료 합니다.
{
stack[top]=start;//스택의 탑에는 시작 정점을 입력 합니다.
break;
}
}
printf("\n");
pathprint(stack,top,j);//스택에 입력된 값을 출력 합니다.
}
printf("\n");
}
void pathprint(int stack[],int top,int j)//스택값을 출력 합니다.
{
int i;
printf("%d : ",j);
for(i=top;i>=0;i--)
{
printf("%3d",stack[i]);
}
}

키워드

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