최단 경로의 개수 구하기

어떤 최단 경로 문제든 최단 경로의 개수를 구하는 방법은 똑같습니다. 현재 방문한 꼭짓점 $u$가 꼭짓점 $v$와 가중치 $w$인 변으로 연결되어 있을 때 $d(v) > d(u) + w$이면 $d(v)$를 $d(u)+w$로 업데이트하고 $c(v)$에 $c(u)$를 대입합니다. 물론 동시에 적절히 큐나 우선순위 큐에도 넣어주면 되죠. $d(v) = d(u) + w$이면 $c(v)$에 $c(u)$를 더해주면 됩니다. 여기서 $d(v)$은 꼭짓점 $v$까지 가는 최단 거리이고 $c(v)$는 그 최단 거리의 개수입니다. 시작점 $s$에서는 당연히 $d(s)=0$, $c(s)=1$입니다.

응용

BOJ 11084:: 나이트의 염탐

icpc.me/11084

BFS로 최단 경로의 개수를 구하는 문제입니다. 가중치 $w$는 모두 1이라고 가정하고 최단 경로의 개수 배열 $c$를 업데이트 하면 됩니다.

BOJ 14554:: The Other Way

icpc.me/14554

다익스트라 알고리즘으로 최단 경로의 개수를 구하는 문제입니다.