まずは頂点 \(1\) から頂点 \(N\) までの最短距離を求める問題を考えてみましょう。辺の重みが全て \(1\) であることから、この問題はBFS(幅優先探索)を用いることで \(O(N+M)\) で解くことができます。

元の問題も同様に、BFSを用いて \(O(N+M)\) で解くことができます。始点からの距離だけでなく、それを達成する経路の数も同時に計算します。

最短距離を求めるBFSでは、最短距離を表す配列を\(\text{dist}\) として

• \(v\) から遷移できる各 \(v'\) に対して次を行う
  • \(v'\) に未到達なら \(\text{dist}[v']\) を \(\text{dist}[v]+1\) に更新
  • そうでないなら何もしない

という処理をしますが、最短経路の数を表す配列 \(\text{cnt}\) を新たに用意することで、次のように更新することができます。

• \(v\) から遷移できる各 \(v'\) に対して次を行う
  • \(v'\) に未到達なら \(\text{dist}[v']\) を \(\text{dist}[v]+1\) に更新し、\(\text{cnt}[v']\) に \(\text{cnt}[v]\) を代入する
  • \(v'\) に到達済みかつ \(\text{dist}[v']=\text{dist}[v]+1\) なら、\(\text{cnt}[v']\) に \(\text{cnt}[v]\) を加算する
  • そうでないなら何もしない

実装例(Python)

# 入力の読み込み
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	A,B=map(int,input().split())
	A-=1
	B-=1
	G[A].append(B)
	G[B].append(A)

# 初期化
que=[0]
dist=[None]*N
cnt=[0]*N
dist[0]=0
cnt[0]=1

# BFS
for v in que:
	for vv in G[v]:
		if dist[vv] is None:
			dist[vv]=dist[v]+1
			que.append(vv)
			cnt[vv]=cnt[v]
		elif dist[vv]==dist[v]+1:
			cnt[vv]+=cnt[v]
			cnt[vv]%=10**9+7

print(cnt[N-1])