언어 자료구조 알고리즘/[C++]디딤돌 자료구조와 알고리즘

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

언제나휴일 2016. 4. 12. 15:01
반응형

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 형식을 정점으로 할 거예요. 정점을 보관하는 vectorVertexs 이름으로 타입 재지정하세요.

typedef vector<string> Vertexs;

typedef Vertexs::iterator VIter;

typedef Vertexs::const_iterator CVIter;

 

Edge *를 보관하는 vectorEdges 이름으로 타입 재지정하세요.

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;

 

경험 정보를 보관하는 vectorHeues로 타입 재지정할게요.

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)

                {

 

만약 후보 테이블의 전체 비용이 더 크면 교체해야 하므로 checkfalse로 변경하세요.

                    if((*seek)->GetWeight()<(*hseek)->GetWeight())

                    {                                               

                        check = false;                        

                    }

반복문을 탈출합니다.

                    break;

                }

            }

만약 hseekhlast와 같다는 것은 후보 테이블에 없는 것입니다.

            if(hseek == hlast)

            {

우선 순위 큐와 후보 테이블에 보관합니다.

                hq.push(*seek);//큐에 보관

                htable.push_back(*seek);

            }

            else

            {

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

                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++]


반응형