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;
}
}```

### 댓글

댓글 본문
작성자
비밀번호
버전 관리
 2017-08-10 11:25:34 vztpv
현재 버전 2017-08-10 11:25:34
graphittie 자세히 보기
• 토픽 0
• 모듈 0
• 코스 0
• 봤어요 0
• 댓글 0
• 명예의 전당 0