여행 경로 계획 프로그램 (Travel Path Planner) < Shortest Path Problem, Dijkstra Algorithm >

main.cpp

#include "Planner.h"

int main()
{
 Planner test;

 if(!test.Start("input.txt", "output.txt")) cout << "Error Occured.. (no route or input error)";

 return 0;
}

Planner.h

#ifndef PLANNER_H
#define PLANNER_H

#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <stack>
using namespace std;


class Edge // list에 이용될 클래스
{
public:
 int id;
 int cost;
 int time;
 Edge* next;
};

class Planner
{
private:
 Edge* graph; // 여행 경로 그래프
 queue<int> main_route; // 주 여행 경로 (여행지 번호;V)
 queue<Edge*> route; // 최적의 여행 경로 (엣지;E)
 int* found; // 경로 찾기에서 해당되거나 제외될 여행지 번호를 저장

 int number_of_vertices; // 여행지 갯수
 int number_of_edges; // 여행지간 연결 간선의 갯수
 double Wm,Wt; // 소요비용과 시간의 만족도 가중치 (Wm+Wt=1)

 double Utility(Edge* e) { return (e->cost*Wm + e->time*Wt); }
public:
 bool Start(char* filename, char *outname); // 파일을 읽어서 경로를 찾고 출력하는 함수
 bool DijkstraAlgorithm(int start, int end); // shortest(여기선 lowest) path 알고리즘
};
#endif

Planner.cpp

#include "Planner.h"

bool Planner::Start(char *filename, char *outname) // filename -> input 파일 이름
{
 fstream File,Output;
 char c;
 int n,t,start,end,total,dup;
 int s[4];
 double r;
 Edge* temp;
 string output_route;

 // 파일 읽고 클래스 멤버에 저장, 멤버 초기화
 File.open(filename,ios::in);
 if(!File) return false;

 n = 0;
 //t = 0;
 do
 {
  t=0;
  switch(n)
  {
  case 0:
   File >> number_of_vertices;
   File.get(c);
   n++;
   break;
  case 1:
   do
   {
    File.get(c);
    if(c == ' ') 
    {
     main_route.push(t);
     t = 0;
     continue;
    }
    else if(c == '\n')
    {
     main_route.push(t);
     break;
    }
    else
    {
    t = t * 10;
    t = t + (c - '0');
    }
   } while(1);
   graph = new Edge[number_of_vertices];
   found = new int[number_of_vertices];
   for(int i=0;i<number_of_vertices;i++)
   {
    graph[i].id = i+1;
    graph[i].cost = 0;
    graph[i].time = 0;
    graph[i].next = NULL;
   }
   n++;
   break;
  case 2:
   File >> number_of_edges;
   File.get(c);
   n++;
   break;
  case 3:
   for(int i=0;i<number_of_edges;i++)
   {
    File >> s[0];
    File >> s[1];
    File >> s[2];
    File >> s[3];
    File.get(c);
   
    for(temp=&graph[s[0]-1];temp->next;temp=temp->next) {};    
    temp->next = new Edge();
    temp = temp->next;

    temp->id = s[1];
    temp->cost = s[2];
    temp->time = s[3];
    temp->next = NULL;
   }
   n++;
   break;
  case 4:
   File >> r;
   Wm = r;
   File >> r;
   Wt = r;
   n++;
   break;
  default:
   return false;
  }
 } while(n != 5);
 File.close();
 // 파일 읽기 끝

 // 시작점과 도착점 저장
 start = main_route.front();
 end = main_route.back();
 // 끝


 // 결과 경로 큐에 시작점을 미리 넣어둔다.
 route.push(&graph[start-1]);


 // 도착점을 찾을때까지 경로를 결과루트에 저장
 while(route.back()->id != end)
 {
  // 주요 경로 차례대로 경로를 찾기 위해 큐를 순환시킨다
  main_route.push(main_route.front());
  main_route.pop();
  // 끝

  // 주요경로1 -> 주요경로2 까지의 경로를 찾는다. (함수 내에서 결과 루트 큐에 엣지 포인터를 집어넣음
  if(!this->DijkstraAlgorithm(route.back()->id,main_route.front())) return false;

 }

 // 주요 경로 큐를 올바른 순서로 되돌리려고 사용
 main_route.push(main_route.front());
 main_route.pop();
 //끝

 
 // 출력하기 위해 계산 및 기록하는 부분
 Output.open(outname,ios::out);

 // 방문 배열 초기화~_~
 for(int i=0;i<number_of_vertices;i++)
  found[i] = 0;
 //끝

 total = dup = 0; // total = 총 방문한 도시 수, not_main = 중복 방문 도시 수
 r = 0; // Total utility of final route!!!!!! (double) 
 while(!route.empty()) // 결과 경로 큐가 비어있을때까지 (모든 결과 경로 출력)
 {
  total++;
  r = r + this->Utility(route.front()); // total utility 계산 (누적)
  c = route.front()->id + '0'; // 여행지 번호를 문자로 변환

  // 주요 경로인지 아닌지 확인한다
  // (주 경로도 다시 방문할 수 있으므로 주석처리)
 // is_main = false;
 // for(int i=0,s=main_route.size();i<s;i++)
 // {
 //  if(main_route.front() == route.front()->id) 
 //  {
 //   is_main=true; // 주요 경로이면 true.. (나중에쓰임)
 //   break;
 //  }
//
//   // 주요 경로 큐 순환
  // 주석처리로인해 할 필요 없다.
//   main_route.push(main_route.front());
//   main_route.pop();
//  }
  //끝

  // 중복 방문 도시인지 확인
  if(found[route.front()->id-1])
   dup++;
  else
   found[route.front()->id-1] = 1;
  //끝

  // 경로를 순차적으로 출력하는 부분을 위해 string에 저장
  if(route.front()->cost == 0 && route.front()->time == 0) 
   // cost와 time이 0인 엣지라면 (list에서 graph배열의 엣지 값은 0이다. 즉 출발점;Vertices)
   // graph배열의 next 값 부터 weighted edge..
  {
   output_route = "(";
   output_route = output_route + c;
   output_route = output_route + ")";
   main_route.pop();
  }
  else // 시작점이 아니면 ( 화살표 추가 )
  {
   if(!main_route.empty()&&main_route.front() == route.front()->id) // 주요 경로에 포함되어있다면 괄호 추가 (단 한번만)
   {
    output_route = output_route + "->(";
    output_route = output_route + c;
    output_route = output_route + ")";
    main_route.pop();
   }
   else // 아니면 그냥 출력.
   {
    output_route = output_route + "->";
    output_route = output_route + c;
  
   }
  }

  route.pop(); // 결과 경로 큐에서 삭제
 }

 // 소숫점 둘째자리까지 표시
 Output.precision(2); // 2 digit
 Output.setf(ios::fixed,ios::floatfield);
 cout.precision(2); // 2 digit
 cout.setf(ios::fixed,ios::floatfield);
 //끝

 // 쓰기 (파일&화면)
 Output << r << endl;
 Output << output_route << endl;
 Output << "(" << total << ")-(" << dup << ")=(" << total-dup << ")";
 cout << r << endl;
 cout << output_route << endl;
 cout << "(" << total << ")-(" << dup << ")=(" << total-dup << ")";


 Output.close();
 cout << endl << endl;
 // 출력 끝!


 // 초기화
 while(!main_route.empty())
  main_route.pop();

 while(!route.empty())
  route.pop();
 // 끝

 return true;
}

bool Planner::DijkstraAlgorithm(int start, int end)
{

//    id와 graph 배열의 인덱스는 1만큼 차이가 난다
//   id-1 = index!!!
   

 int minpos,v; //minpos = U가 최소인 vertices의 인덱스
 double min; // U(i)의 최소값
 int* tree; // 백트래킹 배열
 stack<int> box; // 백트래킹 결과를 뒤집어 줄 stack

 // 백트래킹 배열 초기화
 tree = new int[number_of_vertices];

 // graph,fount 초기화
 for(int i=0;i<number_of_vertices;i++)
 {
  found[i] = 0;
  graph[i].time = 99999;
  graph[i].cost = 99999;
 }

 // 주 여행 경로를 클라우드에서 제외한다
 //for(int i=0,s=main_route.size();i<s;i++)
 //{
 // found[main_route.front()-1] = 1;
 // main_route.push(main_route.front());
 // main_route.pop();
 //}
 //끝

 // 시작점 초기화
 found[start-1] = 1; // 클라우드에 시작점을 포함하는 것으로 한다
 graph[start-1].cost = 0;
 graph[start-1].time = 0;
 tree[start-1] = start-1; // 백트래킹 배열 저장
 

 // 도착점 초기화 (start에서 이 함수를 호출하는 방법 때문에 end는 주 여행 경로의 번호임)
 found[end-1] = 0;

 // 시작점과 연결된 여행지에 엣지의 코스트와 타임을 대입
 for(Edge* p=graph[start-1].next;p!=NULL;p=p->next)
 {
  if(!found[p->id-1]) // 주 여행 경로가 아니거나 도착점의 경우
  {
   tree[p->id-1] = start-1;
   graph[p->id-1].cost= p->cost;
   graph[p->id-1].time = p->time;
  }
 }

 // Dijkstra Algorithm을 통한 V 업데이트
 //for(int i=0,prev=start;i<number_of_vertices-static_cast<int>(main_route.size())+2-2;i++)
  // i<n-2.. n=총 여행지 수 - 주 여행지 수 + (시작점+도착점)..
 for(int i=0,prev=start;i<number_of_vertices-2;i++)
 {
  // U가 최소인 여행지 선택
  minpos = -1;
  min = 99999;
  for(int j=0;j<number_of_vertices;j++)
  {
   if(!found[j] && this->Utility(&graph[j]) < min)
   {
    minpos = j;
    min = this->Utility(&graph[j]);    
   }
  }

  // minpos가 존재하지 않는다? input error 또는 경로가 없음
  if(minpos == -1) return false;

  // U가 최소인 여행지 클라우드에 포함시킨다
  found[minpos] = 1;

  // 선택된 여행지와 연결된 경로들로 다른 여행지의 값들을 업데이트 시킨다 
  for(Edge* p=graph[minpos].next;p!=NULL;p=p->next)
  {

   if(this->Utility(&graph[minpos]) + this->Utility(p) < this->Utility(&graph[p->id-1]))
   {
    tree[p->id-1] = minpos; // 백트래킹 배열 저장
    graph[p->id-1].cost = graph[minpos].cost + p->cost;
    graph[p->id-1].time = graph[minpos].time + p->time;
   }

  }

 prev=minpos;

 }

 // 백트래킹 패스를 stack에 넣어 순서를 원래대로 해준다 
 v=end-1;
 while(v!=tree[v])
 {
  box.push(v);
  v=tree[v];
 }
 
 // 경로에 해당되는 엣지 포인터를 결과 경로 큐에 집어넣는다!
 while(!box.empty())
 {
  for(Edge* p=graph[route.back()->id-1].next;p!=NULL;p=p->next)
  {
   if(p->id-1 == box.top())
   {
    route.push(p);
    break;
   }
  }

  box.pop();
 }

 // vertices들을 다시 0으로 초기화한다.. (안하면 Dijkstra algorithm 작동 안됨)
 for(int i=0;i<number_of_vertices;i++)
 {
  graph[i].cost = 0;
  graph[i].time = 0;
 }
 

 //return false;
 return true;
}