230719 강의

다익스트라 알고리즘에 대해서 강의했습니다. 그래픽적으로 표현하지 않고 먼저 콘솔창으로 시작해서 나중에 그래픽으로 나타낸다고 했습니다.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <queue>

using namespace std;

class DiNode
{
    friend class Di;
private:
    string  id;
    bool    find;
    string  prev;
    unordered_map< string, int> linkedList;

    //              key   cost
public:
    int     cost;   //현재까지 비용
    DiNode(string id)
    {
        this->id = id;
    }
    void Print()
    {
        cout << id;
    }
    void Link(string node , int cost)
    {
        linkedList[node] = cost;
    }
    void Reset()
    {
        prev = "NULL";
        cost = INT_MAX;
        find = false;
    }
    float GetCost() { return cost; }
};

class DiNodeCompare
{
public:
    bool operator()(DiNode*& a, DiNode*& b)
    {
        return a->cost > b->cost;
    }
};

class Di
{
    //중복없는 키, 임의접근
       //            key   node
    unordered_map< string, DiNode*> list;
public:

    DiNode*& AddNode()
    {
        int number = 'A';
        string str;
        str = (char)number;
        for (auto it = list.begin(); it != list.end(); it++)
        {
            number++;
            str = (char)number;
        }

        DiNode* temp = new DiNode(str);
        list[str] = temp;
        return temp;
    }
    
    bool PopNode(string str)
    {
        auto it = list.find(str);
        if (it != list.end())
        {
            delete it->second;
            list.erase(str);
            return true;
        }
        return false;
    }

    void LinkNode(string str1, string str2, int cost)
    {
        list[str1]->Link(str2, cost);
        list[str2]->Link(str1, cost);
    }

    void AllPrint()
    {
        for (auto it = list.begin(); it != list.end(); it++)
        {

            it->second->Print();
            cout << ",";
        }
    }

    vector<DiNode*> PathFinding(string from, string to)
    {
        for (auto it = list.begin(); it != list.end(); it++)
        {
            it->second->Reset();
        }
        priority_queue<DiNode*, vector<DiNode*>, DiNodeCompare> 
            Searchlist;

        Searchlist.push(list[from]);
        list[from]->cost = 0;
        list[from]->find = true;

        while (not Searchlist.empty())
        {
            DiNode* top = Searchlist.top();
            Searchlist.pop();

            for (auto it = top->linkedList.begin();
                it != top->linkedList.end(); it++)
            {
                //기존노드의 비용 갱신
                if (list[it->first]->cost > top->cost + it->second)
                {
                    list[it->first]->cost = top->cost + it->second;
                    list[it->first]->prev = top->id;
                    if (not list[it->first]->find)
                    {
                        Searchlist.push(list[it->first]);
                        list[it->first]->find = true;
                    }
                }
            }
            vector<DiNode*> way;

            DiNode* iter = list[to];
            way.push_back(iter);
            while (1)
            {
                iter = list[iter->prev];
                way.push_back(iter);
                if (iter->id == from)
                {
                    break;
                }
            }
            return way;
        }
    }
};

int main()
{
    string from, to;
    Di di;

    di.AddNode();
    di.AddNode();
    di.AddNode();
    di.AddNode();
    di.AddNode();
    di.AddNode();
    di.AddNode();
    di.AddNode();
    di.AddNode();

    di.LinkNode("A", "B", 3);
    di.LinkNode("A", "C", 4);
    di.LinkNode("B", "D", 3);
    di.LinkNode("B", "C", 4);
    di.LinkNode("B", "E", 3);
    di.LinkNode("C", "D", 4);
    di.LinkNode("C", "I", 4);
    di.LinkNode("D", "E", 4);
    di.LinkNode("D", "F", 6);
    di.LinkNode("D", "H", 2);
    di.LinkNode("D", "I", 5);
    di.LinkNode("E", "F", 5);
    di.LinkNode("F", "G", 4);
    di.LinkNode("G", "H", 3);
    di.LinkNode("H", "I", 5);

    while (1)
    {
       cout << "출발지를 입력해주세요";
       cin >> from;
       cout << "도착지를 입력해주세요";
       cin >> to;
      vector<DiNode*> way = di.PathFinding(from, to);
      cout << "경로는:";
      for (int i = 0; i < way.size(); i++)
      {
          way[i]->Print(); cout << "->";
      }
    }
}

아직 이대로는 실행되지 않고 노드 제거도 되지 않으며 오류가 납니다. 다음날 완성 되었을 때 올리겠습니다.

 

읽어주셔서 감사합니다.