C++로 쉽게 풀어쓴 자료구조 프로그래밍 12장 Dijkstra & Floyd 알고리즘 예제

AdtMatGraph.h와 WGraph.h는 http://jaimemin.tistory.com/252?category=970810 참고하시기 바랍니다.

[WGraphDijkstra.h]

#include "WGraph.h"

 

class WGraphDijkstra :public WGraph

{

private:

        int dist[MAX_VTXS]; //시작노드로부터의 최단경로 거리

        bool found[MAX_VTXS]; //방문한 정점 표시

public:

        //방문하지 않은 정점들 중에서 최단 경로 거리가 가장 작은 정점을 찾아 반환

        int chooseVertex()

        {

               int min = INF;

               int minpos = -1;

               for (int i = 0; i < size; i++)

               {

                       if (dist[i] < min && !found[i])

                       {

                              min = dist[i];

                              minpos = i;

                       }

               }

               return minpos;

        }

        //Dijkstra의 최단 경로 알고리즘:start 정점에서 시작함

        void ShortestPath(int start)

        {

               for (int i = 0; i < size; i++)

               {

                       dist[i] = getEdge(start, i);

                       found[i] = false;

               }

               found[start] = true; //시작노드 방문 표시

               dist[start] = 0; //최초거리

               for (int i = 0; i < size; i++)

               {

                       cout << "Step" << i + 1 << ": ";

                       printDistance();

                       int u = chooseVertex();

                       found[u] = true;

                       for (int w = 0; w < size; w++)

                       {

                              if (found[w] == false)

                                      if (dist[u] + getEdge(u, w) < dist[w])

                                              dist[w] = dist[u] + getEdge(u, w);

                       }

               }

        }

        void printDistance() //dist 상태를 출력하는 함수

        {

               for (int i = 0; i < size; i++)

                       cout << dist[i] << "\t";

               cout << endl;

        }

};

 

[Dijkstra Main]

#include "WGraphDijkstra.h"

 

int main(void)

{

        WGraphDijkstra g;

        g.load("graph_sp.txt");

        cout << "Shortest Path By Dijkstra Algorithm" << endl;

        g.ShortestPath(0);

        return 0;

}

[텍스트 파일, Floyd 알고리즘에서도 동일하게 사용]

[WGraphFloyd.h]

/*

Floyd의 최단 경로 프로그램

*/

#include "WGraph.h"

 

class WGraphFloyd :public WGraph

{

private:

        int A[MAX_VTXS][MAX_VTXS]; //최단경로 거리

public:

        void ShortestPathFloyd()

        {

               for (int i = 0; i < size; i++)

                       for (int j = 0; j < size; j++)

                              A[i][j] = getEdge(i, j);

 

               for (int k = 0; k < size; k++)

               {

                       for (int i = 0; i < size; i++)

                              for (int j = 0; j < size; j++)

                                      if (A[i][k] + A[k][j] < A[i][j])

                                              A[i][j] = A[i][k] + A[k][j];

                       printA();

               }

        }

        void printA()

        {

               cout << "===================================================" << endl;

               for (int i = 0; i < size; i++)

               {

                       for (int j = 0; j < size; j++)

                       {

                              if (A[i][j] == INF)

                                      cout << "INF\t";

                              else

                                      cout << A[i][j] << "\t";

                       }

                       cout << endl;

               }

        }

};

[Floyd Main]

#include "WGraphFloyd.h"

 

int main(void)

{

        WGraphFloyd g;

        g.load("graph-Floyd.txt");

        cout << "Shortest Path by Floyd Algorithm" << endl;

        g.ShortestPathFloyd();

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] C++로 쉽게 풀어쓴 자료구조