Dijkstra 法で \(G\) から各駅への最短移動時間を求めておく. これを \(d(i)\) とする.

ある頂点 \(i\) まで時間 \(t\) で移動できたとする. このとき, 頂点 \(i, j\) が移動時間 \(t_j\) でつながっているとすると, \(t+t_j+d(j) = d(S)\) となる頂点に移動した場合は最短経路をたどっているので, この中で最小の \(j\) を求める.