11.3.1 다익스트라 알고리즘 구현 [디딤돌 자료구조와 알고리즘 with c++]

11.3.1 다익스트라 알고리즘 구현

이번에는 다익스트라 알고리즘을 구현해 보아요. 그래프와 Heuristic 부분은 깊이 우선 탐색과 너비 우선 탐색에서 구현한 것과 매우 흡사합니다.

다익스트라 알고리즘.zip

 

먼저 간선 클래스를 정의합시다.

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;

}

 

 

방문한 정정 목록을 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;

}

 

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);

            }

            else

            {

후보 테이블에 있을 때는 교체해야 하는지를 확인하세요. check가 false면 교체해야 합니다.

                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 

11.3 다익스트라 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

11.3.2 다익스트라 알고리즘 코드 [디딤돌 자료구조와 알고리즘 with C++]