최단경로알고리즘 구현

Code:

#include<iostream> #include<queue> #include<list> using namespace std; #define M 10000 #define countOfVtx 5 int dist[countOfVtx]; void Dijkstra(int (*G)[countOfVtx], int s) {    list<int> V1, V2;   // vertex = set(V1) + set(V2)    int path[countOfVtx];   //s에서 countOfVtx까지의 최단거리    int i, j, min, minJ;    for(i=0;i<countOfVtx;i++)    {       if(G[s][i]!=-1)   //s에 대해 RELAX       {          dist[i]=G[s][i];          path[i]=s;       }       else          dist[i]=M;   //dist 초기화       if(i!=s)          V2.push_back(i);   //v2에는 s를 제외한 모든 점 삽입    }    dist[s]=0;    list<int>::iterator location2;    while(!V2.empty())    {       min=M;       location2 = V2.begin();       for(j=0;j<V2.size();j++,location2++)       {          if(dist[*location2]<min)          {             min=dist[*location2];             minJ=*location2;          }       }       V2.remove(minJ);       location2=V2.begin();       //RELAX       for(i=0;i<V2.size();i++,location2++)          if(G[minJ][*location2]!=-1)             if(dist[*location2]>dist[minJ]+G[minJ][*location2])             {                dist[*location2]=dist[minJ]+G[minJ][*location2];                path[*location2]=minJ;             }       s=minJ;    } } bool BellmanFord(int (*G)[countOfVtx+1], int s)   //newG에 대해서 실행하므로 countOfVtx+1; {    int len[countOfVtx+1] = { 0 };   //weight를 제거한 단순 edge개수    int newDist[countOfVtx+1];    queue<int> Q;    int i,j=0,start;    for(i=0;i<countOfVtx+1;i++)       newDist[i]=M;    newDist[s]=0;    Q.push(s);   //시작점0을 큐에 넣는다.    while(!Q.empty())   //만약 G내에 음수의 싸이클이 있다면 무한루프에 빠진다.    {       start=Q.front();       if(len[start]>countOfVtx+1)   //만약 G내에 음수의 싸이클이 있다면 빠져나가자          return(false);       for(i=0;i<countOfVtx+1;i++)   //start점에서 각 점으로 edge가 있으면       {          if(G[start][i]!=M && newDist[i]>newDist[start]+G[start][i])          {             newDist[i]=newDist[start]+G[start][i];             Q.push(i);             len[i]=len[start]+1;          }       }       Q.pop();    }    for(i=0;i<countOfVtx;i++)       dist[i]=newDist[i];    return true; } void Johnson(int (*G)[countOfVtx]) {    //=====newG 생성===== 정점 s를 추가한 그래프    int newG[countOfVtx+1][countOfVtx+1];    int i, j;    for(i=0;i<countOfVtx;i++)   // 새로운 정점 s의 번호는 countOfVtx    {       newG[i][countOfVtx]=M;       newG[countOfVtx][i]=0;       for(j=0;j<countOfVtx;j++)          newG[i][j]=G[i][j];    }    newG[countOfVtx][countOfVtx]=0;    //=====nonnegative weight 생성=====    if(BellmanFord(newG, countOfVtx)==false)    {       cout<<"It contains a negative weight cycle!"<<endl;       exit(1);    }    else    {       for(i=0;i<countOfVtx;i++)   //for each edge (u, v) (in E[newG])          for(j=0;j<countOfVtx;j++)             if(newG[i][j]!=M)                G[i][j]=newG[i][j]+dist[i]-dist[j];       //=====각 정점에서 다익스트라 실행=====       for(i=0;i<countOfVtx;i++)   //for each vertex u(in V[G])       {          cout<<"\n- 정점 "<<i+1<<"에서 다익스트라 알고리즘 실행 -"<<endl;           Dijkstra(G, i);          for(j=0;j<countOfVtx;j++)          {             //newG2[i][j]=G[i][j]+dist[j]-dist[i];   //다시 원래대로 돌려주기 위하여~             cout<<j+1<<"("<<dist[j]<<")  ";          }          cout<<endl;       }    }    } void main() {    int G[countOfVtx][countOfVtx]={       {M, 3, 8, M,-4},       {M, M, M, 1, 7},       {M, 4, M, M, M},       {2, M,-5, M, M},       {M, M, M, 6, M}    };   //M은 10000... 무한대로 가정    Johnson(G); }