[C++] 5월 19일 코딩 테스트 수업

다익스트라 알고리즘

 

#pragma once

#include <iostream>
#include <map>


class C_DIJKSTRA
{
private:
	struct S_NODE
	{
		int nId;
		std::map<S_NODE*, int> child;

		bool bVisit;
		S_NODE* pParent;
		int nLength;

		bool operator()(S_NODE* Dst, S_NODE* Src)
		{
			return Dst->nLength > Src->nLength;
		}

		//bool operator()(S_NODE& Dst, S_NODE& Src)
		//{
			//return Dst.nLength > Src.nLength;	
		//}
	};

private:																																																																																			
	std::map<int, S_NODE*> m_mapNode;

private:
	S_NODE* findCreateNode(int nId);

public:
	C_DIJKSTRA() = default;
	void add(int nDst, int nSrc, int nLenght);
	void print();
	void make(int nNode);
};

 

 

#include "Dijkstra.h"
#include <queue>

C_DIJKSTRA::S_NODE* C_DIJKSTRA::findCreateNode(int nId)
{
	auto iterResult = m_mapNode.insert({ nId, nullptr});

	if (iterResult.second)
	{
		iterResult.first->second = new S_NODE{};
		iterResult.first->second->nId = nId;
		iterResult.first->second->nLength = INT_MAX;
	}

	return iterResult.first->second;
}

void C_DIJKSTRA::add(int nDst, int nSrc, int nLenght)
{
	S_NODE* pDst = findCreateNode(nDst);
	S_NODE* pSrc = findCreateNode(nSrc);

	pDst->child.insert({ pSrc, nLenght });
	pSrc->child.insert({ pDst, nLenght });
}

void C_DIJKSTRA::print()
{
	for (auto iter : m_mapNode)
	{
		printf("id : %d ->", iter.first);

		for (auto iterChild : iter.second->child)
		{
			printf("(%d, %d)", iterChild.first->nId, iterChild.second);
		}
		printf("\n");
	}
}

void C_DIJKSTRA::make(int nNode)
{
	std::priority_queue<S_NODE*, std::vector<S_NODE* >, S_NODE> heap{};

	S_NODE* pNode = m_mapNode.find(nNode)->second;
	pNode->nLength = 0;
	heap.push(pNode);

	while (!heap.empty())
	{
		S_NODE* pParent= heap.top();
		heap.pop();

		if (!pParent->bVisit)
		{
			pParent->bVisit = true;

			for (auto pChild : pParent->child)
			{
				if (pParent->nLength + pChild.second < pChild.first->nLength)
				{
					pChild.first->nLength = pParent->nLength + pChild.second;
					pChild.first->pParent = pParent;
					heap.push(pChild.first);
				}
			}
				//부모의 길이값과 pChild.second값의 합이 
				//pChild.first->nLength 보다 작으면 부모교체 length값 교체 
				//heap에 다시 push 

		}
	}
}

void C_DIJKSTRA::printPath()
{
	for (const auto& pair : m_mapNode)
	{
		S_NODE* node = pair.second;
		printf("Node %d : Distance = %d, Parent = %d\n",
			node->nId,
			node->nLength,
			node->pParent ? node->pParent->nId : -1);
	}
}

 

 

#include <iostream>
#include "Dijkstra.h"

int main()
{
	C_DIJKSTRA cDijkstra{};
	
	cDijkstra.add(1, 2, 3);
	cDijkstra.add(1, 3, 4);

	cDijkstra.add(2, 3, 5);
	cDijkstra.add(2, 4, 10);
	cDijkstra.add(2, 6, 9);

	cDijkstra.add(3, 4, 8);
	cDijkstra.add(3, 5, 5);

	cDijkstra.add(4, 5, 6);
	cDijkstra.add(4, 6, 10);
	cDijkstra.add(4, 7, 7);
	cDijkstra.add(4, 8, 3);

	cDijkstra.add(5, 7, 4);

	cDijkstra.add(6, 8, 2);

	cDijkstra.add(7, 8, 5);

	cDijkstra.make(1);
	cDijkstra.print();
}