سوال ۶۱ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱

The single-source-to-a-set trick

We must output $d(u,S)=\min_{v\in S}\delta(u,v)$ for every vertex $u$ — that is $n$ values. A naive plan (run Dijkstra from each $u$, or from each $v\in S$) costs many shortest-path computations. The exam wants the one-shot construction.

Step 1 — reverse the edges

Distances $\delta(u,v)$ are from $u$ to a sink in $S$. Build the reverse graph $G^{R}$ (flip the direction of every edge, keeping weights). Then $\delta_{G}(u,v)=\delta_{G^{R}}(v,u),$ so now we need, for each $u$, the shortest distance to $u$ from the nearest source in $S$.

Step 2 — add a super-source

Add one new vertex $s$ and a $0$-weight edge $s\to v$ for every $v\in S$. In $G^{R}$ the shortest distance from $s$ to $u$ is $\delta_{G^{R}}(s,u)=\min_{v\in S}\bigl(0+\delta_{G^{R}}(v,u)\bigr)=\min_{v\in S}\delta_{G}(u,v)=d(u,S).$ So a single single-source shortest-path run from $s$ produces all $n$ answers simultaneously.

Step 3 — pick the algorithm and count

All weights are positive, so Dijkstra applies. The augmented graph has $|V'| = n+1=\Theta(n),\qquad |E'| = \underbrace{O(n)}_{\text{original}} + \underbrace{|S|}_{\le\, n} = O(n)$ edges — the graph is sparse. Dijkstra with a binary heap runs in $O\bigl((|V'|+|E'|)\log|V'|\bigr)=O(n\log n).$

Hence all $d(u,S)$ values are computed in $\boxed{O(n\log n)}$ — option 4.

Exam trick: "shortest distance to the nearest vertex of a set" = reverse the edges + a single $0$-weight super-source + one Dijkstra. With $O(n)$ edges the binary-heap Dijkstra is $O(n\log n)$; do not multiply by $|S|$ or by $n$.