다익스트라 알고리즘

Graph_SearchDijkstra

cpp파일

#include"Graph_SearchDijkstra.h"

Graph_SearchDijkstra::Graph_SearchDijkstra(string str) : m_fs(str.c_str(), ios::in)
{
 if (!m_fs.is_open())
 {
  cout << "파일읽기 실패" << endl;
  return;
 }
 
 m_fs >> m_nodeNum;
 m_fs >> m_edgeNum;

 m_vW.resize(m_nodeNum);
 m_vS.resize(m_nodeNum);

}

Graph_SearchDijkstra::~Graph_SearchDijkstra()
{
 m_vW.clear();
 m_vS.clear();
 cout << "다익스트라 해제" << endl;
}

void Graph_SearchDijkstra::ReadFile()
{
 int from, to, cost = 0;
 GraphEdge temp;
 while (m_fs.good())
 {
  m_fs >> from;
  m_fs >> to;
  m_fs >> cost;

  
  from -= 1;
  to -= 1;

  temp.SetFrom(from);
  temp.SetTo(to);
  temp.SetCost(cost);

  m_vW[from].push_back(temp);
 }
 cout << m_vW.size() << "개의 노드가 만들어졌습니다" << endl;
}

void Graph_SearchDijkstra::Search()
{
 int start, target = 0;
 cout << "출발지 입력 : ";
 cin >> start;
 start -= 1;
 cout << "도착지 입력 : ";
 cin >> target;
 target -= 1;

 int temp = m_vW.size(); //저장된 노드의 갯수

 vector<double> dist(temp, 999); //노드 개수만큼 거리 d생성(초기화는 무한대)
 dist[start] = 0.0; //거리 d에서 시작 인덱스 0으로 시작거리 초기화

 set<pair<int, int>> pq; //거리값 저장할 set생성, 자동으로 정렬이 되는것이 장점 set<거리값, 인덱스>
 pq.insert(make_pair(0, start)); //시작값을 set에 저장함. 0(거리), start(위치), 왜 거리가 먼저냐면 이걸로 정렬되니까..

 while (!pq.empty()) //최초에 start값이 들어있는 상태에서 반복문 시작
 {
  pair<int, int> top = *pq.begin(); //set에서 최소의 거리값 불러오기
  pq.erase(top); //불러온 최신값 set에서 삭제
  
  int current = top.second; //불러온 최신값에서 현재 인덱스불러옴(start)
  
  if (current == target) //불러온 인덱스와 목표지점이 같다면
  {
   cout << "최종목적지" << current+1 << "찾음" << endl;
   cout << "경로 : ";
   ShowPath(target);
   return;
  }

  vector<GraphEdge> &edge = m_vW[current]; //최소값 인덱스의 에지를 불러옴

  for (int i = 0; i < edge.size(); ++i) //최소값 인덱스의 에지와 연결된 에지의 수를 확인함, 1-2 1-3 이런경우 2개니까..최초 vector<vector<edge>>였다
  {
   //최소값과 무관하게 연결된 순서로 에지를 for문함

   int next = edge[i].To(); //i번째 에지의 to방향의 인덱스를 가져옴
   //거리를 비교
   //위에 왜 to방향의 인덱스가 필요하냐면..다음방향을 나가야하기 떄문이다.
   if (dist[next] > dist[current] + edge[i].Cost()) //직접 to방향 > 현재까지의 값 + to방향의 비용
   {
    //pq는 set이고 거리, 위치 이렇게 저장이됨
    pq.erase(make_pair(dist[next], next)); //to방향의 값이 혹시 들어가있다면 삭제(왜냐면 최신화해야지..값이 작은게 있으니)
    pq.insert(make_pair(dist[current] + edge[i].Cost(), next));//to방향을 새로운 최소값으로 다시 대체

    //dist에 최신화한다 to방향을 새로운 값으로
    dist[next] = dist[current] + edge[i].Cost(); //
    //위치 추적을 위해서 [to방향]=현재값으로 역추적하게 한다
    m_vS[next] = current;
    cout << current+1 << " -> " << next+1 << endl;
    cout << dist[next] << endl;
   }
  }
 }
}

void Graph_SearchDijkstra::ShowPath(int target)
{
 
 int temp = m_vS.size();
 int index = target;
 cout << target+1 << "->";
 for (int i = 0; i < temp; ++i)
 {
  cout << m_vS[index]+1 << "->";
  index = m_vS[index];
  //m_vS[index];
 }//vs를 target인덱스로 값을 불러옴..
 cout << endl;
 /*
 아래 순서는 완전히 엉망임..다시해야함..
 */
 
}

 

header파일

#ifndef _DIJKSTRA_H_
#define _DIJKSTRA_H_

#include"GraphEdge.h"
#include<set>
#include<functional>
#include<fstream>

class Graph_SearchDijkstra
{
public:
 //벡터<에지>의 벡터인 이유는
 //1-2, 1-3 이런걸 표현하기 위해..
 //1은 벡터이고 -2이것은 벡터<에지> 가 된다.
 //그래서 -2 -3 -4이 있으니까..접근성 때문에 []으로 함..
 vector<vector<GraphEdge>> m_vW; //에지 저장백터
 vector<int>     m_vS; //경로 저장백터
 
 fstream      m_fs;

public:
 int       m_nodeNum;
 int       m_edgeNum;

public:
 Graph_SearchDijkstra(string str);
 ~Graph_SearchDijkstra();

 void ReadFile();
 void Search();
 void ShowPath(int target);

};

#endif

 

GraphEdge

header파일

class GraphEdge
{
protected:
 //에지는 두개의 노드를 연결한다 유효한 노드는 항상 양수의 인덱스를 가짐
 int   m_iFrom; //시작
 int   m_iTo;   //도달

 //에지를 따라가는 비용
 int  m_dCost;

public:
 GraphEdge(int from, int to, int cost) : m_dCost(cost), m_iFrom(from), m_iTo(to)
 {}

 GraphEdge(int from, int to) : m_dCost(1.0), m_iFrom(from), m_iTo(to)
 {}

 GraphEdge() : m_dCost(1.0), m_iFrom(invalid_node_index), m_iTo(invalid_node_index)
 {}

 virtual ~GraphEdge(){}

 int From(){ return m_iFrom; }
 void SetFrom(int NewIndex) { m_iFrom = NewIndex; }

 int To(){ return m_iTo; }
 void SetTo(int NewIndex) { m_iTo = NewIndex; }

 int Cost() const{ return m_dCost; }
 void SetCost(int NewCost) { m_dCost = NewCost; }
};

#endif

 

main

int main()
{
 string str("test.txt");
 Graph_SearchDijkstra data(str);
 data.ReadFile();
 data.Search();
 _getch();
 return 0;
}

 

test.txt

5 9
1 2 3
1 3 5
2 1 4
2 5 3
3 4 5
4 1 6
3 1 4
4 5 2
5 4 3

 

5는 노드개수 9는 엣지개수

1은 from 2는 to 3은 cost로 구성..

 

경로를 보여주는 Graph_SearchDijkstra::ShowPath 함수 수정이 필요하나..목적은 달성 나중에 시간되면 수정..

나중에 내용을 다시 확인할 땐 주석부분을 다시 보면서 생각을 조금씩 해보면 될듯..