Как посчитать количество кратчайших путей между двумя вершинами?

Ведём два массива: dist[v] (длина кратчайшего пути) и ways[v] (число кратчайших путей до v). При BFS, когда из v идём в соседа u:

• если нашли u впервые (dist[u] ещё не установлено) → dist[u] = dist[v]+1, ways[u] = ways[v];
• если пришли в u снова по кратчайшему (dist[v]+1 == dist[u]) → ways[u] += ways[v].

const int MOD = 1e9+7;
vector<int> dist(n, -1), ways(n, 0);
queue<int> q;
dist[s] = 0; ways[s] = 1; q.push(s);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int u : g[v]) {
        if (dist[u] == -1) {
            dist[u] = dist[v] + 1;
            ways[u] = ways[v];
            q.push(u);
        } else if (dist[u] == dist[v] + 1) {
            ways[u] = (ways[u] + ways[v]) % MOD;
        }
    }
}
// ответ: ways[t]

Сложность O(V + E). ways обычно считают по модулю — число путей растёт экспоненциально.