So I have been asking myself for a long time these 2 problems:
- Given a graph with N vertices and M edges, find the sum of shortest paths between (u -> v) for every u, v
- Given a graph with N vertices and M edges, answer queries asks for the shortest path between (u -> v)
It is guaranteed that there exists a way to travel from nodes to others.
Constraints: N <= 1e5 , M <= 1e5 , Q <= 1e5(Q is number of queries for the second problem)
Since then, I have been thinking and searching but nothing comes out good enough to pass the constraints.
Is there any way to solve these?
For the first problem, BFS should work. Find the shortest distance of each node from $$$u$$$, and then for each node $$$a$$$ connected to $$$v$$$, check if $$$dist[a] = dist[v]-1$$$. If yes, then add $$$dist[v]$$$ to the answer. This is assuming all the edges have the same weight.
As your algorithm above, I assume that this only works for single source shortest paths. I am sorry but I wrote something wrong, the question is with every u and v in the graph not just with only one start node.
=(((
Auto comment: topic has been updated by Phuong0703 (previous revision, new revision, compare).
Constraints seem to be too big to be solved within the 1 sec time limit. if there was no time limit then this problem can theoretically be solved by floyd-warshall algo which describes the distance between two vertices $$$i$$$ and $$$j$$$ as follows.
where k will be some vertex between the path of $i$ to $$$j$$$
Can read more about it here: Floyd Warshall CP Algo