다익스트라 알고리즘(Djikstra)

다익스트라 알고리즘 소스입니다. 이 소스 공개되면, 각 대학의 Data Structure(자료구조) 혹은 네트워킹 리포트로 이 소스가 사용될 것입니다. 다익스트라 알고리즘은 좀 구하기 힘든것으로 알고 있습니다. 그래서 이 소스가 벨만포드보다 리포트에 많이 사용될 것입니다.

요령것 리포트를 하시길 바라며, 리포트를 베꼈다고 해서 F 맞는 일이 없기를 바랍니다.

참고로...전북 전주에 있는 J모 대학교 컴공과 분들은 사용하지 마세요. 이미 그 교수님께(이름 안밝힘...하지만 이 수업 하는 교수님은 한분임.) 제가 리포트로 작성해서 냈습니다. 그 리포트 자료 교수님 컴퓨터에 그대로 있습니다. 좌절 하지 마시고...다른 소스를 검색하시길 바랍니다.


#include <iostream.h>
#define N 6
#define M 1024
int weight[N+1];
int n[N+1]={0,0,0,0,0,0,0}; //N의 값에 따라 초기화.
int t1[N+1][N+1]; //경로 저장용.
void showDrouting();
void path(int k, int w);
void dijkstra(int c[N+1][N+1])
{
int i, j, k, w, min, count;
int s[N]={0,0,0,0,0,0}; //노드를 다 거쳤는지 확인하기 위한 값. N의 값에 따라 초기화 숫자를 수정한다.
s[1] = 1;
cout<<"I     T      |L(2) path|L(3) path|L(4) path|L(5) path|L(6) path"<<endl; //N의 값에 따라 노드를 늘려준다.

for(i=0;i<=N;i++)
t1[i][0]=1;
for(i=0;i<=N;i++)
{
weight[i]=c[1][i]; // 소스노드(1)에서 다른 노드까지의 거리를 우선 저장.
}
////////////// 첫번째 노드 출력
count=0;
cout<<"1   {";
for(j=0;j<N;j++)
{
if(s[j])
  cout<<j;
else count++;
}
for(j=0;j<count;j++)
cout<<".";
cout<<"} ";
///////////////
showDrouting(); //첫번째 노드에서 갈 수 있는 곳을 출력
for(i=1;i<N-1;i++)
{
min = M;
for(k=2; k<=N;k++)
{
  if(weight[k]!=0)
   if(!s[k]&& (weight[k]<min))
   {
    w=k;
    min = weight[k]; //갈 수 있는 곳 중에서 가장 적은 가중치를 찾아 저장한다.
   }
}
s[w] = 1; //노드를 거쳤다는 표시.
count=0;
cout<<i+1<<"   {";
for(j=0;j<N;j++)
{
  if(s[j])
   cout<<j;
  else count++;
}
for(j=0;j<count;j++)
  cout<<".";
cout<<"} ";
for(k=2; k<=N ; k++)
{
  if(weight[k]!=0)
   if(weight[k]>weight[w]+c[w][k]) //다른 곳을 경우할 경우가 더 빠르다면, 가중치 값을 갱신한다.
   {
    n[k]++;
    weight[k]=weight[w]+c[w][k];
    path(k,w); //그리고 경유하는 곳을 저장한다.
   }
}
showDrouting();
}
}
void path(int k, int w)
{
int m;
m=n[k];
t1[k][m]=w;
}
void showDrouting()
{
int i,j,k,temp;
for(k=2;k<=N;k++)
{
i=0;
j=0;
if(weight[k]!=M)
{
  cout<<"|"<<weight[k]<<"  "; // 가중치를 먼저 출력하고.
  while(t1[k][i]!=0)
  {
   temp=t1[k][i];
   j=1;
   while(t1[temp][j]!=0) //경유하는 곳을 출력한다.
   {
    if(t1[temp][j]!=t1[k][i-1])
     cout<<t1[temp][j]<<"-";
    j++;
   }
   cout<<t1[k][i]<<"-";
   i++;
  }
  cout<<k; //도착점 출력.
  if(k==6)
   cout<<endl;
}
else if(k==6)
{
  cout<<"|"<<weight[k]<<"  --"<<endl;
}
else
{
  cout<<"|"<<weight[k]<<"  --";
}
}
}
void main(void)
{
int array[N+1][N+1] =
{ 0,0,0,0,0,0,0,
0,0,2,5,1,M,M,
0,3,0,3,2,M,M,
0,8,6,0,3,1,5,
0,7,2,3,0,1,M,
0,M,M,1,1,0,2,
0,M,M,8,M,4,0};
cout<<"Dijkstra 알고리즘은 가중치가 양수일 경우 적용됩니다."<<endl;
cout<<"************************************************************"<<endl;
cout<<"Dijkstra Algorithm"<<endl;
cout<<"소스 노드는 1로 설정합니다. 배열의 0번째는 0으로 채웁니다."<<endl;
cout<<"************************************************************"<<endl;
cout<<"노드수는"<<N<<"으로 설정되어 있습니다. 가중치는 양방향입니다."<<endl<<endl;

dijkstra(array);
}