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