[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

출발점, 도착점 사이의 최단 경로를 알아내는 알고리즘,

각 꼭지점은 도시를 나타내고 변은 도로의 길이를 나타날 때,

도시간 최단경로 찾기가 문제이다


최단 경로 찾기에선 가장 간단한 문제 이기도 할 것이다.


일단 5개의 도시로 고정되어있고,

-1은 갈 수 없는 거리 0은 자기 자신을 표현한다.


알고리즘을 대략적으로 설계하면,

for i -> 0 , 5 , 1
[시작도시][i]로 전체를 검사한다.


완전탐색이지만, 예외조건을 둔다

0과 -1을 제외하고, isVisit을 도시크기만큼 2차원 배열을 같이 두어

방문 체크를 한다.

그리고 최소값만을 Return하는 형식을 취하면 될 것 같다.

도시를 출력하고자 한다면, vector를 따로 두어, 경로를 push_back 하면 될 것 같긴하다.

테스트 케이스 및 자료는 [알고리즘 자료] 2-1 을 보시면 있습니다.

#include 
#include 
using namespace std;
int city[5][5] = { 0, };
bool isVisit[5][5] = { false, };
bool isFinal = false;
bool isPossiblePath(int val)
{
 if (val == 0 || val == -1) return false;

 return true;
}

void VisitCheck(int src, int dst)
{
 isVisit[src][dst] = true;
}

void VisitUnCheck(int src, int dst)
{
 isVisit[src][dst] = false;
}
int Dijkstra(int src,int dst,int fDst,int path)
{
 path = path + city[src][dst];
 
 if (dst == fDst)
  return path; // 하나의 경로를 찾은 것
 
 int result = 9999;
 for (int i = 0; i < 5; i++)
 {
  if (!isPossiblePath(city[dst][i]) || isVisit[dst][i] == true) continue;

  int temp = 0;
  VisitCheck(dst, i); // 방문 체크
  temp = Dijkstra(dst, i, fDst, path);
  VisitUnCheck(dst, i); // 방문 체크 해제
  result = min(temp, result);
 }

 
 return result;
}



int _tmain(int argc, _TCHAR* argv[])
{
 FILE *fp = fopen("test.txt", "rt");
 if (fp == NULL)
 {
  cout << "FILE OPEN ERROR" << endl;
  return 0;
 }

 int src,dst = 0;
 fscanf(fp, "%d %d\n", &src, &dst);
 char temp;
 for (int i = 0; i < 5; i++)
  for (int j = 0; j < 5; j++)
   fscanf(fp, "%d%c", &city[i][j], &temp);
  
  int result = 9999;
  
   for (int j = 0; j < 5; j++)
   {
    if (!isPossiblePath(city[src][j])) continue;
        
    int temp;
    VisitCheck(src, j);
    temp = Dijkstra(src, j, dst,0);
    VisitUnCheck(src, j);
    result = min(temp, result);
   }
   if (result == 9999) cout << "도시까지의 경로가 존재하지 않습니다" << endl;
   else 
    cout << result << endl;

 return 0;
}

추가로 읽으면 좋을 것