Given a graph with N nodes with each node numbered from 1 to N and M edges and a target vertex T. Find the number of different ways to reach target vertex T from vertex numbered 1.
2 <= N <= 2 * 10^5,
M = min( 2 * 10^5, N * ( N - 1 ) / 2 )
Time limit — 5sec
Compute the answer modulo 10^9 + 7.
Auto comment: topic has been updated by ALuca_Rd (previous revision, new revision, compare).
Infinite.
Thanks! I didn't thought about that. But if we take the modulo of answer to lets say 10^9 + 7. Then how can we do it.
Taking infinite modulo 10^9+7 doesn't make sense.
He forgot to mention, the graph is directed acyclic.
Then it is a standard DP problem.
Here you can use topological sorting + dp for directed acyclic graph. Link
You can find the number of shortest paths from using this.
First, how can we find the length of the shortest path from Vertex 1 to Vertex N? Since the every edge has weight 1, the question can be answered with a BFS (Breadth-First Search) in a total of
O(N+M)
time.The original problem can similarly be solved with BFS in a total of
O(N+M)
time, in which we compute not only the shortest distance from the starting vertex but also the number of the paths accomplishing the distance.When finding the shortest distance with BFS, we compute the array of shortest distance
dist
by:For each
v′
that has an edge fromv
• if we’ve never visited
v′
yet, updatedist[v]
todist[v]+1
;• otherwise, do nothing.
Simultaneously, we can update a new array of number of shortest path cnt in the following way:
• if we’ve never visited
v′
yet, updatedist[v]
todist[v]+1
and assigncnt[v]
tocnt[v]
;• if we’ve already visited
v′
anddist[v′]
=dist[v]+1
, addcnt[v]
tocnt[v]
;• otherwise, do nothing.
Assuming you are talking about all simple paths on an undirected graph, I don't think your approach works.
3 3
1 2
1 3
2 3
This code worked on a problem from atcoder
Yeah. I didn't see the edit regarding this only works for shortest paths.
You can refer to this Blog it may help you — https://www.baeldung.com/cs/graph-number-of-shortest-paths