최단경로

• Prob
• Solv
• Check
  • case 1 - w가 오름차순
  • case 2 - deque의 문제점
• Ref

최단경로

Prob

노드 V, 엣지 E, 루트 노드 K
u에서 v로 가는 가중치인 간선 존재
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로

Solv

bfs를 사용
queue 대신 priority queue를 사용해서 w를 오름차순으로 정렬 후 기존 값과의 비교를 통해 연산량 단축
루트 노드의 w는 0으로 설정 후 v를 통해 queue에 push할 값 선정
queue에 push하면서 w를 누적
이 때 visit을 누적한 w를 저장하고 기존 w와 비교하여 push하여 결정하는 역할로 사용

Check

case 1 - w가 오름차순

V=5 E=6 K=1

u	v	w
5	1	1
1	2	2
1	3	3
2	3	4
2	4	5
3	4	6

dq(v,w)	now(v,w)
(2,2)(3,3)	(1,0)
(3,3)(3,4+2)(4,5+2)	(2,2)
(4,7)(4,6+3)	(3,3)
	(4,7)

case 2 - deque의 문제점

deque를 사용할 경우 같은 v 중 w가 큰 것이 먼저 들어와서 w가 작은 것이 후에 들어오면 연산을 더하게 됨
(4,7)이 이 후에 들어오면서 visit을 업데이트하면 정답은 나오지만 미리 제외하지 못해 연산이 많아짐

V=5 E=6 K=1

u	v	w
5	1	1
1	3	3
2	3	4
1	2	2
3	4	6
2	4	5

dq(v,w)	now(v,w)
(3,3)()	(1,0)
(2,2)(4,6+3)	(3,3)
(4,9)(3,4+2)(4,5+2)	(2,2)
(4,7)	(4,9)
	(4,7)

Ref

https://yabmoons.tistory.com/376