똑똑한 코드 작성을 위한 실전 알고리즘

262

똑똑한 코드 작성을 위한 실전 알고리즘

➎

힙 순서 속성을 만족하도록

sink(1)

를 실행하기 전에 전체 엔트리 수를 하나 감소한다.

➏

우선순위가 가장 높은 엔트리와 연관된 값을 반환한다 (가장 작은 값 ).

IndexedMinPQ

자료구조는

v

가 우선순위 큐에 저장된 값인 경우 불변을 보장하고,

location

[

v

]

는 인덱스 위치

idx

를 가리키므로

values

[

idx

]

는

v

이고

priorities

[

idx

]

는

v

의 우선순위인

p

가 된다.

다익스트라 알고리즘은 그래프에 지정된

src

노드에서 모든 노드까지 최단 경로 길이를 계산

하는 데

IndexedMinPQ

를 사용한다. 사전 타입 변수

dist

_

to

[

v

]

를 사용해 그래프의

src

에

서 각

v

까지 알려진 최단 계산 경로의 길이를 기록한다. 이 값은

src

에서 도달 가능하지 않은

노드에 대해서는 무한의 값이 된다. 다익스트라 알고리즘은 그래프를 탐색할 때 가중치가

wt

인 간선으로 연결된 두 노드

u

와

v

를 찾는다 (

dist

_

to

[

u

] +

wt

<

dist

_

to

[

v

]

와 같이 ). 즉,

src

에서

v

까지 거리는

src

에서

u

까지의 경로를 찾은 뒤에 간선

(

u

,

v

)

를 따라

v

로 가는 편이

더 짧다.

다익스트라 알고리즘은 이와 같이 특별한 간선을 체계적으로 찾는 방법을 보여주며, 이

는 너비 ...