It’s easy to calculate the number of different shortest paths from a certain starting point using Dijkstra.

Let’s say $cnt1_i$ represents the number of different shortest paths from vertex $1$ to vertex $i$, and $d1_i$ represents the minimal distance from vertex $1$ to vertex $i$.

Similarly, let $cnt2_i$ represent the number of different shortest paths from vertex $n$ to vertex $i$, and $d2_i$ represent the minimal distance from vertex $n$ to vertex $i$.

A key insight is that, for a bidirectional edge $(u,v)$ with weight $w$, if the number of shortest path from $1$ to $n$ that pass $(u,v)$ equals $cnt1_n$ implies all shortest paths include this edge, thus the answer is Yes.

Specifically, the answer for such an edge is Yes if either of the following holds:

• $d1_u + d2_v + w = d1_n$ and $cnt1_u \times cnt2_v = cnt1_n$

• $d1_v + d2_u + w = d1_n$ and $cnt1_v \times cnt2_u = cnt1_n$

The only problem is that the number of different shortest paths may be too large to store. To solve this, use multi-hashing, and the problem can be easily solved.

Sample code