答えは \(\{\text{dist}(s,j)+\text{dist}(j,t)-\text{dist}(s,t)\}/2+1\) なので(下図参照) \(s\) と \(t\) からそれぞれ単一始点最短路をすれば求まります。

s

|

o

|

o ＝ o ＝ o ＝ o ＝ o ＝ j

|

o

|

t