플로이드&다익스트라 알고리즘

알고리즘 분석 수업 과제로 제출한 플로이드&다익스트라 알고리즘 코드입니다.

본격적으로 코딩을 시작한지 얼마 되지 않아서 아직 부족한 점이 많지만 참고하시고, 부족한 부분은 피드백 부탁드려요!

// 입출력 라이브러리를 사용하기 위하여(하단의 cout)
#include <iostream>
using namespace std;
 
#define V 5 // 정점의 수
// 알고리즘을 위한 공통 설정
#define INF 100000 // 무한대 (경로가 존재하지 않을 때를 의미, 임의의 큰 수로 설정)
int start_vertex = -1;
int end_vertex = -1;
 
// 플로이드 알고리즘을 위한 배열
int D[V][V] = { 0, }; //최단 거리값을 저장할 배열
int P[V][V] = { 0, }; //최단 거리 경로를 저장할 배열
 
// 플로이드
  // 플로이드 알고리즘의 결과를 출력하는 함수
  void printfloyd(int D[V][V])
  {
    // 결과표의 가로축(꼭짓점 번호는 1번부터 시작)
      cout << "from↓  ";
      for (int i = 0; i < V; i++) {
        cout.width(4);
        cout << "[" << i+1 << "]";
      }
      cout << " ←to " << endl;
 
    // 결과표의 세로축
      for (int i = 0; i < V; i++) // 정점 i+1에서
        {
            cout << "   [" << i+1 << "]";
            for (int j = 0; j < V; j++) // 정점 j+1로 가는
            {
                if (D[i][j] == INF) // 배열은 0번부터 넣을 예정이기 때문
                    {cout.width(6); cout << "INF";} // 경로가 없는 경우
                else
                    {cout.width(6); cout << D[i][j];} //최단 경로가 존재함
            }
            cout << endl;
        }
      cout << "-------------------------------------------" << endl;
 
  }
 
  // 플로이드 알고리즘 2 : 시작정점에서 종료정점까지의 최단 거리 경로 구하기
  // 주의할 것! 값은 배열 인덱스로 들어오는데, 검색해서 찾아내는 값은 +1이 된 값이다.
  void floyd_path (int from, int to) // 배열 인덱스로 들어온다
  {
    if( P[from][to] != 0 ) // 직전 정점이 있으면
    {
      int path_vertex = P[from][to];  // path_vertex는 P배열 안에 있는 +1 된 값이기 떄문에
      floyd_path (from, path_vertex -1 ); // 왼쪽 재귀 함수 ()배열 인덱스에 맞게 -1함)
      cout << path_vertex << "->" ; // 출력되는 값은 원래 값 그대로여야 함.
      floyd_path(path_vertex -1 , to ); // 오른쪽 재귀 함수
    }
  }
 
  void print_floyd_path (int from, int to)
  {
      cout << from + 1 << "->"; // 시작정점
      floyd_path(from, to);
      cout << to+1 << endl; // 종료 정점
  }
 
  // 플로이드 알고리즘 1 : 그래프에서 모든 꼭짓점 사이의 최단 경로의 길이를 구하기
  void floyd(int graph[V][V], int from, int to)
  {
      int i; // 시작 정점값
      int j; // 종료 정점값
      int k; // 중간에 거쳐가는 정점값
 
      for (i = 0; i < V; i++)
          for (j = 0; j < V; j++){
              D[i][j] = graph[i][j]; // 그래프의 초기값(플로이드 알고리즘을 실행할 배열)을 D배열에 복사함
          }
 
      for (k = 0; k < V; k++) // 정점 k+1을 반드시 경유하여
      {
          for (i = 0; i < V; i++) // 정점 i+1점에서
          {
              for (j = 0; j < V; j++) // 정점 j+1점으로 갈 떄
              {
    // 시작정점(i+1 정점)에서 경유정점(k+1)까지의 거리와 경유정점(k+1)에서 종료정점(j+1)까지의 거리를 합한 값이
    // 시작정점(i+1)에서 종료정점(j+1)까지의 기존 값보다 짧다면 최단거리를 갱신한다.
                  if (D[i][k] + D[k][j] < D[i][j]){
                      D[i][j] = D[i][k] + D[k][j];
                      P[i][j] = k+1;
                  }
              }
          }
        printfloyd(D); //출력
      }
 
      cout << "  2) 플로이드 알고리즘 종료 직전 정점 P배열 " << endl;
      printfloyd(P);
 
      cout << "  3) 플로이드로 구한 시작점 "<< from+1 <<"(으)로부터 " << to+1 <<" 까지의 최단 경로 : ";
      print_floyd_path(from, to); //경로 출력
      cout << "-------------------------------------------------------------" << endl;
  }
 
// 다익스트라
  // 다익스트라 알고리즘의 결과 도출 과정을 출력하는 함수
  void printDijstra(bool found[], int distance[], int previous[], int start)
  {
      cout << "Vertex  Found   Distance   Previous Vertex" << endl;
      for (int i = 0; i < V; i++) {
        cout.width(3); cout << i+1; // ppt에 정점을 1부터 시작했기 때문에 배열의 번호에 1을 더해줌.
        cout.width(8); cout << found[i];
        cout.width(12); cout << distance[i];
        cout.width(12); cout << previous[i] << endl;
        }
      cout << "-------------------------------------------" << endl;
  }
 
  // 알려진 정점에서 가장 가까운 정점을 찾는 함수
  int find_nearest_vertex(bool found[V], int distance[V])
  {
      int nearest_distance = INF;
      int nearest_vertex = -1;
 
      for (int i = 0; i < V; i++)
      {
        //최단거리가 알려지지 않은 정점 중에서, 거리가 가장 짧은 것을 반환
          if (!found[i] && nearest_distance > distance[i])
          {
              nearest_vertex = i;
              nearest_distance = distance[i];
          }
      }
 
      return nearest_vertex;
  }
 
  // 다익스트라 알고리즘 2 : 다익스트라 알고리즘으로 최단 경로 구하기
  // 주의할 것! 값은 배열 인덱스로 들어오는데, 검색해서 찾아내는 값은 +1이 된 값이다.
  void dijkstra_path (int previous[V], int to) // 배열 인덱스로 들어온다
  {
    if( previous[to] != INF )
    {
      int pre_vertex = previous[to];
      dijkstra_path ( previous, pre_vertex -1 );
      cout << pre_vertex << "->" ;
    }
  }
 
  void print_dijkstra_path (int previous[V], int from, int to)
  {
      dijkstra_path(previous, to);
      cout << to+1 << endl;
  }
 
  // 다익스트라 알고리즘 1 : 시작점에서 각 정점까지의 최단 거리를 구하는 알고리즘
  void dijkstra(int graph[V][V], int from, int to)
  {
      int distance[V]; // 시작 정점에서 현재 정점까지의 거리
      bool found[V]; // 최단 거리이면 ture, 아니면 false
      int previous[V];
 
      // 배열의 초기화
      for (int i = 0; i < V; i++)
          distance[i] = INF, found[i] = false, previous[i] = -1;
 
      // 시작점 설정
      distance[from] = 0; // 시작점의 거리는 0
      previous[from] = INF; // 시작점의 이전 정점은 없으므로 INF 처리함
 
      for (int count = 0; count < V; count++)
      {
          // 최단거리 정보를 알고 있는 노드들 중 가장 거리가 짧은 노드의 인덱스를 가져온다.
          int found_vertex = find_nearest_vertex(found, distance);
          found[found_vertex] = true;
 
          for (int i = 0; i < V; i++)
          {
              // 아직 최단거리로 확정되지 않은 정점들 중에 && 시작점으로 순환하지 않으며 && 기존의 최단거리보다 해당 정점을 거쳐서 가는 거리가 더 짧다면
              if (found[i]==false && previous[i]!=INF && distance[i] > distance[found_vertex] + graph[found_vertex][i])
              {
                  // 최단거리를 갱신
                  distance[i] = distance[found_vertex] + graph[found_vertex][i];
                  previous[i] = found_vertex+1;
              }
          }
 
          // 현재까지의 최단 거리를 출력해준다.
          printDijstra(found, distance, previous, from);
      }
 
      cout << "  2) 다익스트라로 구한 시작점 "<< from+1 <<"(으)로부터 " << to+1 <<" 까지의 최단 경로 : ";
      print_dijkstra_path(previous, from, to); //경로 출력
      cout << "-------------------------------------------------------------" << endl;
 
  }
 
void show_graph(int graph[V][V])
{
    cout << "0. 초기 그래프" << endl;
  // 가로축
    cout << "from↓  ";
    for (int i = 0; i < V; i++) {
      cout.width(4);
      cout << "[" << i+1 << "]";
    }
    cout << " ←to " << endl;
 
  // 세로축
    for (int i = 0; i < V; i++)
      {
        cout << "   [" << i+1 << "]";
        for (int j = 0; j < V; j++){
          // cout.width(6);
          if (graph[i][j] == INF)
            {cout.width(6); cout << "INF";}
          else {cout.width(6); cout << graph[i][j];}
        }
        cout << endl;
      }
    cout << "-------------------------------------------------------------" << endl;
}
 
 
int main()
{
    int graph[V][V] =
    {
      // //교재에 나온 코드로 알고리즘이 잘 작동하는지 확인 가능
      //   {0,1,INF,1,5},
      //   {9,0,3,2,INF},
      //   {INF,INF,0,4,INF},
      //   {INF,INF,2,0,3},
      //   {3,INF,INF,INF,0},
 
        // 피피티에 설명한 초기 그래프
        {0, 17, 8, 1, INF},
        {INF, 0, 3, INF, INF},
        {15, INF, 0, INF, INF},
        {INF, 7, 6, 0, 9},
        {10, 12, INF, 2, 0},
    };
 
    show_graph(graph);
 
    cout << "알고리즘의 시작 정점을 입력해주세요 : ";
    cin >> start_vertex;
    cout << "알고리즘의 종료 정점을 입력해주세요 : ";
    cin >> end_vertex;
    cout << "-------------------------------------------------------------" << endl;
 
    //플로이드 알고리즘으로 계산
    cout << "1. 플로이드 알고리즘 "<< endl;
    cout << "  1) 모든 정점 사이의 최단 거리를 구하는 과정" << endl;
    floyd(graph, start_vertex-1, end_vertex-1);
 
    // 다익스트라 알고리즘으로 계산
    cout << "2. 다익스트라 알고리즘 "<< endl;
    cout << "  1) 시작점 "<< start_vertex <<"에서 각 정점까지 가는 최단 경로를 구하는 과정" << endl;
    dijkstra(graph, start_vertex-1, end_vertex-1); // 정점은 1부터 배열은 0부터 시작해서
 
    return 0;
}