C++로 자료구조 구현하기

- 응용 : Dijkstra algorithm

/// init vertex
for (Vertex& v : vertex)
{
	v.distance = WrapForInfinity<int>::GetInfinity();
	v.index = -1;
	v.no = count++;
	minHeap.push(&v);
}
/// init edge
//
edge = makeTestEdge(MAX);

vertex[0].distance = WrapForInfinity<int>(0);
vertex[0].parent = -1;
minHeap.update(vertex[0].index);

while (!minHeap.empty())
{
	/// Extract-Min : u <= Q.
	Vertex* pVertex = minHeap.pop();
	pVertex->index = 0; /// chk..
	///  for 각각� 정점 v Adj[u]
	const int no = pVertex->no;
	Edge* pEdge = edge[no].next;

	while (NULL != pEdge)
	{
		const int no2 = pEdge->last; /// vertex no..
		/// Do Relax( u, v, w )
		if (vertex[no2].distance == WrapForInfinity<int>::GetInfinity() ||
			(vertex[no2].distance.val > (vertex[no].distance.val + pEdge->weight.val)))
		{
			/// d[v] <- d[u] + w(u,v)
			vertex[no2].distance = WrapForInfinity<int>(vertex[no].distance.val + pEdge->weight.val);
			vertex[no2].parent = no;

			/// update queue
			minHeap.update(vertex[no2].index);
		}
		/// next
		pEdge = pEdge->next;
	}
}

댓글

댓글 본문
작성자
비밀번호
버전 관리
vztpv
현재 버전
선택 버전
graphittie 자세히 보기