이번에는 다익스트라 알고리즘을 구현해 보아요. 그래프와 Heuristic 부분은 깊이 우선 탐색과 너비 우선 탐색에서 구현한 것과 매우 흡사합니다.
먼저 간선 클래스를 정의합시다.
class Edge
{
두 개의 정점과 간선의 비용이 멤버로 필요하겠죠.
string vt1;
string vt2;
int weight;
두 개의 정점과 간선의 비용을 입력 인자로 받게 생성자를 제공하세요.
public:
Edge(string vt1,string vt2,int height);
특정 정점이 존재하는지 두 개의 정점 모두 존재하는지 판별하는 메서드를 제공하세요.
bool Exist(string vt)const;
bool Exist(string vt1, string vt2)const;
하나의 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 제공하세요.
string Other(string vt)const;
간선 정보를 출력하는 메서드를 제공하세요.
void View()const;
간선의 비용을 구하는 메서드를 제공하세요.
int GetWeight()const; };
생성자는 입력 인자로 받은 값으로 멤버 필드를 설정하게 구현하세요.
Edge::Edge(string vt1,string vt2,int weight)
{
this->vt1 = vt1;
this->vt2 = vt2;
this->weight = weight;
}
특정 정점이 존재하는지 판별하는 메서드를 구현하세요.
bool Edge::Exist(string vt)const
{
return (vt1 == vt)||(vt2==vt);
}
두 개의 정점 모두 존재하는지 판별하는 메서드를 구현하세요.
bool Edge::Exist(string vt1, string vt2)const
{
return Exist(vt1) && Exist(vt2);
}
하나의 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 구현하세요.
string Edge::Other(string vt)const
{
if(vt1 == vt)
{
return vt2;
}
if(vt2 == vt)
{
return vt1;
}
return "";
}
간선의 정보를 출력하는 메서드를 구현하세요.
void Edge::View()const
{
cout<<"("<<vt1<<","<<vt2<<","<<weight<<")";
}
간선의 비용을 구하는 메서드를 구현하세요.
int Edge::GetWeight()const
{
return weight;
}
이제 그래프 클래스에 관해 정의합시다. 먼저 string 형식을 정점으로 할 거예요. 정점을 보관하는 vector를 Vertexs 이름으로 타입 재지정하세요.
typedef vector<string> Vertexs; typedef Vertexs::iterator VIter; typedef Vertexs::const_iterator CVIter;
Edge *를 보관하는 vector를 Edges 이름으로 타입 재지정하세요.
typedef vector<Edge *> Edges; typedef Edges::iterator EIter; typedef Edges::const_iterator CEIter;
그래프 클래스를 정의합시다.
class Graph
{
그래프 클래스에는 정점 집합과 간선 집합을 기억하는 멤버가 필요하겠죠.
Vertexs vertexs;
Edges edges;
그래프 내에서 생성한 간선들을 소멸하기 위해 소멸자를 제공하세요.
public:
~Graph(void);
정점을 추가하는 메서드를 제공합시다.
bool AddVertex(string vt);
정점이 존재하는지 판별하는 메서드를 제공합시다.
bool Exist(string vt)const;
간선을 추가하는 메서드를 제공합시다.
bool AddEdge(string vt1, string vt2,int weight);//간선 추가
두 개의 점점을 잇는 간선이 존재하는지 판별하는 메서드를 제공하세요.
bool Exist(string vt1,string vt2)const;
모든 정점의 이웃 목록을 출력하는 메서드를 제공하세요.
void ViewNeighbors()const;
특정 정점의 이웃 목록을 출력하는 메서드를 제공하세요.
void ViewNeighbor(string vt)const;
특정 정점의 이웃 목록을 구하는 메서드를 제공하세요.
Vertexs FindNeighbors(string vt)const;
특정 정점을 끝점으로 하는 간선 집합을 구하는 메서드를 제공하세요.
Edges FindEdges(string vt)const; };
소멸자에서는 간선 집합에 있는 모든 간선을 소멸하세요.
Graph::~Graph(void)
{
EIter seek = edges.begin();
EIter last = edges.end();
for( ;seek != last; ++seek)
{
delete (*seek);//간선 소멸
}
}
정점을 추가하는 메서드를 구현합시다.
bool Graph::AddVertex(string vt)
{
만약 입력 인자로 받은 정점이 있으면 추가하지 않고 없을 때만 추가합니다.
if(Exist(vt))
{
return false;
}
vertexs.push_back(vt);
return true;
}
정점이 존재하는지 판별하는 메서드를 구현하세요.
bool Graph::Exist(string vt)const
{
return find(vertexs.begin(),vertexs.end(),vt) != vertexs.end();
}
두 정점을 끝점으로 하는 간선을 추가하는 메서드를 구현합시다.
bool Graph::AddEdge(string vt1, string vt2,int weight)//간선 추가
{
if(Exist(vt1)&&Exist(vt2))
{
두 개의 정점이 모두 존재해야 합니다.
if(Exist(vt1,vt2))
{
두 개의 정점을 끝점으로 하는 간선이 이미 있으면 추가하지 않습니다.
return false;
}
여기에서는 간선의 무게 순으로 간선 집합에 추가합시다.
CEIter seek = edges.begin();
CEIter last = edges.end();
for( ;seek != last; ++seek)
{
처음으로 새로 추가하는 간선의 비용보다 크거나 같은 위치를 찾으세요.
if((*seek)->GetWeight()>=weight)
{
위치를 찾으면 반복문을 탈출하세요.
break;
}
}
찾은 위치에 새로운 간선을 생성하여 보관하세요.
edges.insert(seek,new Edge(vt1,vt2,weight));
return true;
}
두 개의 정점 중에 없는 정점이 있을 때는 추가하지 않았으므로 거짓을 반환하세요.
return false; }
두 개의 정점을 끝점으로 하는 간선이 있는지 판별하는 메서드를 구현하세요.
bool Graph::Exist(string vt1,string vt2)const
{
CEIter seek = edges.begin();
CEIter last = edges.end();
for( ;seek != last; ++seek)
{
if((*seek)->Exist(vt1,vt2))
{
return true;
}
}
return false;
}
모든 정점의 이웃 정점 목록을 출력하는 메서드를 구현하세요.
void Graph::ViewNeighbors()const
{
cout<<"=== 이웃 정점 ==="<<endl;
CVIter seek = vertexs.begin();
CVIter last = vertexs.end();
for( ;seek != last; ++seek)
{
cout<<(*seek)<<"의 이웃: ";
ViewNeighbor(*seek);//특정 정점의 이웃 보여주기
}
cout<<endl;
}
특정 정점의 이웃 정점 목록을 출력하는 메서드를 구현하세요.
void Graph::ViewNeighbor(string vt)const
{
CEIter seek = edges.begin();
CEIter last = edges.end();
for( ;seek != last; ++seek)
{
if((*seek)->Exist(vt))
{
cout<<(*seek)->Other(vt)<<" ";
}
}
cout<<endl;
}
특정 정점의 이웃 정점들을 구하는 메서드를 구현하세요.
Vertexs Graph::FindNeighbors(string vt)const
{
Vertexs neighbors;
CEIter seek = edges.begin();
CEIter last = edges.end();
for( ;seek != last; ++seek)
{
입력 인자로 받은 정점을 포함하는 간선이 있으면 나머지 정점이 이웃입니다.
if((*seek)->Exist(vt))
{
neighbors.push_back((*seek)->Other(vt));
}
}
조사한 이웃 집합을 반환합니다.
return neighbors; }
특정 정점을 끝점으로 하는 간선 집합을 구하는 메서드를 제공하세요.
Edges Graph::FindEdges(string vt)const
{
Edges neighbors;
CEIter seek = edges.begin();
CEIter last = edges.end();
for( ;seek != last; ++seek)
{
입력 인자로 받은 정점을 포함하는 간선이 있으면 추가하세요.
if((*seek)->Exist(vt))
{
neighbors.push_back(*seek);
}
}
조사한 간선 집합을 반환합니다.
return neighbors; }
Heuristic 클래스 부분을 구현합시다. 먼저 방문한 정정 목록을 Foots로 타입 재지정하세요.
typedef vector<string> Foots; typedef Foots::iterator FIter; typedef Foots::const_iterator CFIter;
경험 정보를 보관하는 vector를 Heues로 타입 재지정할게요.
class Heuristic; typedef vector<Heuristic *> Heues; typedef Heues::iterator HIter; typedef Heues::const_iterator CHIter;
경험 정보 클래스를 구현합시다. 이 부분도 앞에서 구현한 것과 대부분 비슷합니다.
class Heuristic
{
그래프와 지나온 정점 목록과 전체 비용을 멤버로 선언하세요.
Graph *graph;
Foots foots;
int weight;
그래프와 출발 정점을 입력 인자로 받습니다.
public:
Heuristic(Graph *graph, string start);
다음 경험 정보 목록을 구하는 메서드를 제공합시다.
Heues EnumNext();
현재까지 방문한 경로를 출력하는 메서드를 제공합시다.
void View()const;
현재까지 경로의 비용을 구하는 메서드를 제공하세요.
int GetWeight()const;
가장 마지막에 방문한 정점을 구하는 메서드를 제공하세요.
string GetLastVertex()const;
현재 경험에서 특정 정점을 추가 방문하는 생성자를 제공하세요. 이 생성자는 클래스 내부에서만 사용합니다.
private:
Heuristic(const Heuristic *bheu,string vt,int weight);
};
생성자에서는 입력 인자로 받은 값으로 멤버를 설정하세요
Heuristic::Heuristic(Graph *graph,string start)
{
this->graph = graph;
foots.push_back(start);
전체 비용은 0으로 초기화하세요.
weight = 0; }
다음 Heuristic 목록을 조사하여 반환하는 EnumNext 메서드를 구현합시다.
Heues Heuristic::EnumNext()
{
Heues nheues;
현재 방문한 마지막 정점을 구합니다.
string last_foot = (*foots.rbegin());
마지막 방문한 정점을 끝점으로 하는 간선 집합을 구하세요.
Edges edges = graph->FindEdges(last_foot);
간선 집합을 순차적으로 순회해야죠.
EIter eseek = edges.begin();
EIter elast = edges.end();
for( ;eseek != elast; ++eseek)
{
반복자 위치의 간선에서 나머지 정점을 구합니다.
string other = (*eseek)->Other(last_foot);//간선의 나머지 정점 구하기
방문한 적이 있는지 판별하세요. 방문한 적이 없으면 나머지 정점을 방문하는 새로운 경험을 생성합니다.
if(find(foots.begin(), foots.end(),other) == foots.end())//방문한 적이 없으면
{
Heuristic * nheu = new Heuristic(this,other,(*eseek)->GetWeight());
새로운 경험을 비용 순으로 보관하기 위한 자리를 찾습니다.
HIter hseek = nheues.begin();
HIter hlast = nheues.end();
for( ;hseek != hlast; ++hseek)
{
if((*hseek)->GetWeight()>=nheu->GetWeight())
{
break;
}
}
찾은 위치에 새로운 경험을 보관하세요.
nheues.insert(hseek,nheu);//*seek를 추가 방문하는 새로운 경험을 생성
}
}
다음 경험 목록을 반환합니다.
return nheues; }
방문한 경로를 출력하는 메서드를 구현하세요.
void Heuristic::View()const
{
cout<<"cost "<<weight<<" :";
CFIter seek = foots.begin();
CFIter last = foots.end();
for( ;seek != last; ++seek)
{
cout<<(*seek)<<" ";
}
cout<<endl;
}
전체 비용과 마지막 정점을 구하는 메서드를 구현하세요.
int Heuristic::GetWeight()const
{
return weight;
}
string Heuristic::GetLastVertex()const
{
return (*foots.rbegin());
}
이전 경험에서 새로운 정점을 추가 방문하는 생성자를 구현하세요.
Heuristic::Heuristic(const Heuristic *bheu,string vt,int weight)
{
this->graph = bheu->graph;
foots = bheu->foots;
비용은 이전 경험의 비용에 새로운 비용을 추가한 비용으로 설정하세요.
this->weight = bheu->weight + weight;//경로의 비용을 추가
foots.push_back(vt);//vt를 방문한 행적에 추가
}
이제 다익스트라 알고리즘을 구현할 차례입니다. 우선 순위 큐에서 비교할 함수 개체를 정의하세요.
struct HGreater
{
bool operator()(const Heuristic *h1, const Heuristic *h2) const
{
return h1->GetWeight()> h2->GetWeight();
}
};
다익스트라 알고리즘은 진입점 main 함수에 작성할게요.
int main()
{
먼저 그래프를 생성하고 정점 및 간선을 추가하세요.
Graph *graph = new Graph();//그래프 동적 생성
graph->AddVertex("A");
graph->AddVertex("B");
graph->AddVertex("C");
graph->AddVertex("D");
graph->AddVertex("E");
graph->AddVertex("F");
graph->AddVertex("G");
graph->AddVertex("H");
graph->AddVertex("I");
graph->AddEdge("A", "B", 3);//간선 추가
graph->AddEdge("A", "C", 4);//간선 추가
graph->AddEdge("B", "C", 4);//간선 추가
graph->AddEdge("B", "D", 3);//간선 추가
graph->AddEdge("B", "E", 3);//간선 추가
graph->AddEdge("C", "D", 3);//간선 추가
graph->AddEdge("C", "I", 4);//간선 추가
graph->AddEdge("D", "E", 4);//간선 추가
graph->AddEdge("D", "F", 6);//간선 추가
graph->AddEdge("D", "H", 2);//간선 추가
graph->AddEdge("D", "I", 5);//간선 추가
graph->AddEdge("E", "F", 5);//간선 추가
graph->AddEdge("F", "G", 4);//간선 추가
graph->AddEdge("G", "H", 3);//간선 추가
graph->AddEdge("H", "I", 5);//간선 추가
graph->ViewNeighbors();
다익스트라 알고리즘은 우선 순위 큐가 필요합니다.
priority_queue<Heuristic *,vector<Heuristic *>, HGreater > hq;
그리고 각 정점으로 가는 최단 거리 후보 목록을 기억해야 합니다.
Heues htable;
여기에서는 경험 정보를 여러 자료 구조에 보관하여 소멸의 책임을 지기 편하게 모든 경험 정보를 보관하는 별도의 자료 구조를 선언하세요.
Heues all;
초기 경험 정보를 생성하여 큐에 보관하세요.
Heuristic *heu = new Heuristic(graph,"A");//초기 경험 정보를 생성
hq.push(heu);//큐에 보관
큐가 빌 때까지 반복하세요.
while(hq.empty() == false) //반복(큐가 비어 있지 않다면)
{
큐에서 경험 정보를 꺼내옵니다.
heu = hq.top();//큐에서 경험 정보 꺼내옮
hq.pop();
all.push_back(heu);
cout<<"찾는중 ";
heu->View();
꺼내온 경험 정보에서 다음 경험 목록을 조사합니다.
Heues nheues = heu->EnumNext();//큐에서 꺼내온 경험 정보에서 다음 경험 목록 조사
다음 경험 목록을 순차적으로 순회합니다.
HIter seek = nheues.begin();
HIter last = nheues.end();
for( ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)
{
새로운 경험 정보의 마지막 정점이 후보 테이블에 이미 있는지 확인해야 합니다.
HIter hseek = htable.begin();
HIter hlast = htable.end();
새로운 경험 정보의 마지막 정점을 구하세요.
string nvt = (*seek)->GetLastVertex();
교체하지 않았는지 판별하는 변수를 true로 초기화하세요.
bool check = true;
후보 테이블을 순회합니다.
for( ;hseek != hlast; ++hseek)
{
반복자의 위치의 경험 정보에서 마지막 정점을 구합니다.
string hvt = (*hseek)->GetLastVertex();
새로운 경험 정보의 마지막 정점과 후보 테이블의 현재 경험 정보의 마지막 정점이 같은지 확인해야죠.
if(nvt == hvt)
{
만약 후보 테이블의 전체 비용이 더 크면 교체해야 하므로 check를 false로 변경하세요.
if((*seek)->GetWeight()<(*hseek)->GetWeight())
{
check = false;
}
반복문을 탈출합니다.
break;
}
}
만약 hseek가 hlast와 같다는 것은 후보 테이블에 없는 것입니다.
if(hseek == hlast)
{
우선 순위 큐와 후보 테이블에 보관합니다.
hq.push(*seek);//큐에 보관
htable.push_back(*seek);
}
후보 테이블에 있을 때는 교체해야 하는지를 확인하세요. check가 false면 교체해야 합니다.
else
{
if(check == false)
{
후보 테이블에서 제거하세요.
htable.erase(hseek);
후보 테이블에 새로운 경험으로 보관하세요.
htable.push_back(*seek);
우선 순위 큐에도 보관합니다.
hq.push(*seek);
}
}
}
}
후보 테이블에는 출발지에서 나머지 모든 정점으로 가는 최단 경로가 남아있습니다.
HIter hseek = htable.begin();
HIter hlast = htable.end();
cout<<"A에서의 최단 경로"<<endl;
for( ;hseek != hlast; ++hseek)
{
(*hseek)->View();
}
사용했던 모든 경험 정보를 소멸하세요.
HIter aseek = all.begin();
HIter alast = all.end();
for( ;aseek != alast; ++aseek)
{
delete (*aseek);
}
return 0;
}
▷ 실행 결과
=== 이웃 정점 === A의 이웃: B C B의 이웃: E D A C C의 이웃: D I B A D의 이웃: H C B E I F E의 이웃: B D F F의 이웃: G E D G의 이웃: H F H의 이웃: D G I I의 이웃: C H D 찾는중 cost 0 :A 찾는중 cost 3 :A B 찾는중 cost 4 :A C 찾는중 cost 6 :A B D 찾는중 cost 6 :A B E 찾는중 cost 8 :A B D H 찾는중 cost 8 :A C I 찾는중 cost 11 :A B E F 찾는중 cost 11 :A B D H G 찾는중 cost 12 :A B D F A에서의 최단 경로 cost 3 :A B cost 4 :A C cost 6 :A B D cost 6 :A B E cost 8 :A C I cost 8 :A B D H cost 11 :A B E F cost 11 :A B D H G