벨만포드 알고리즘 소스(BellmanFord)

벨만포드 알고리즘 소스입니다. 이 소스 공개되면, 각 대학의 Data Structure(자료구조) 혹은 네트워킹 리포트로 이 소스가 사용될 것입니다. 인터넷에 벨만포드 소스가 없는 것은 아니지만, 간단한 소스는 찾기가 좀 힘듭니다.

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

외국사이트 검색해보면 몇개 나오긴 합니다. 좀 독특한 소스를 얻으려면 외국 검색기도 이용해보세요.

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

#include <iostream.h>
#include <stdlib.h>
#define Max 1024
#define n 6
void BellmanFord();
void showBMrouting();
void path(int q, int r);
// int W[n][n]={0,2,5,1,Max,Max,
//  3,0,3,2,Max,Max,
//  8,6,0,3,1,5,
//  7,2,3,0,1,Max,
//  Max,Max,1,1,0,2,
//  Max,Max,8,Max,4,0
// };
int W[n][n];
int D[n][n]; //length;
int P[n][n]; //path
void main()
{
int node, i, j, temp;
node=n;
cout<<"******************************************************"<<endl;
cout<<"직접 연결되지 않은 노드는 1024로 표현해시기 바랍니다."<<endl;
cout<<"현재 노드의 수는 "<<node<<"개 입니다."<<endl;
cout<<"******************************************************\n"<<endl;
for(i=0;i<=node-1;i++)
for(j=0;j<=node-1;j++)
{
  cout<<i+1<<"에서 "<<j+1<<"의 가중치를 입력하세요. :";
  cin>>temp;
  W[i][j]=temp;
}
cout<<"최소비용 알고리즘."<<endl;
cout<<"******************************************"<<endl;
cout<<"1. Bellman-Ford Algorithm"<<endl;
BellmanFord(); 
cout<<"\n=====Bellman-Ford====="<<endl;
showBMrouting();
}
void BellmanFord()
{
int i,j,k,x;
for(i=0;i<=n-1;i++) 
for(j=0;j<=n-1;j++) 
  P[i][j]=0; //초기화
for(i = 0; i <= n - 1; i++) 
for(j = 0; j <= n - 1; j++) 
  D[i][j] = W[i][j]; 
for(x = 0; x <= n - 2; x++) // N - 1 반복 
for(k = 0; k <= n - 1; k++) // 소스 
  for(i = 0; i <= n - 1; i++) // 도착지점
   for(j = 0; j <= n - 1; j++) // 노드.
    if(k != i) 
     if(D[k][j] + W[j][i] < D[k][i]) 
     { 
      D[k][i] = D[k][j] + W[j][i]; //짧은 가중치를 적용한다.
      P[k][i] = j + 1; //짧게 가기 위해 전 노드의 값을 저장한다.
     } 
}
void showBMrouting() 
{ 
int i, j; 
for(i = 0; i <= n - 1; i++) 
{ 
cout<<"소스 노드가 "<<i+1<<"일 때"<<endl;
cout<<"Node \t Length \t Path"<<endl;
for(j = 0; j <= n - 1; j++) 
  if(i != j) 
  { 
   cout<<j+1<<" \t "<<D[i][j]<<" \t "<<i+1<<" -> ";
   path(i + 1, j + 1); 
   cout<<j+1<<endl;//path함수에서 마지막 경로까지 다 출력하면 도착노드를 출력하고 줄을 넘긴다.
  } 
} 
cout<<endl;
}
void path(int q, int r) 
{ 
if(P[q - 1][r - 1] != 0) 
{ 
path(q, P[q - 1][r - 1]); //재귀 호출로 경로를 호출한다.
cout<<P[q-1][r-1]<<" -> ";
path(P[q - 1][r - 1], r); //자기 노드에서 자기 노드의 가중치가 있을 경우 표시한다.
} 
}