Abdelrahman_Elhawary's blog

Number of shortest paths
By Abdelrahman_Elhawary, 5 years ago, In English

In a directed Graph of N nodes and M edges what is the maximum number of Shortest paths from any node U to another node V ?

And the same for undirected Graph ?

My question came from this problem 1321D - Navigation System where i needed to calculate the number of paths from any node to node t and didn't know whether long long will fit the maximum number of paths or not

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

The number of shortest paths can be exponential. With a source, 3 other nodes, and 4 edges, you can make 2 shortest paths, by adding 3 more nodes and 4 more edges, you can get 4 paths. So at least you can have $$$2^{M/4}$$$ shortest paths.

Spoiler
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Maybe there are tests with a large number of shortest paths, and your solution passed because it computes the number of paths mod $$$2^{64}$$$.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Abdelrahman_Elhawary (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

I slightly modified the bfs code.

counter[i] will be no more than the number of edges entering the vertex. This information is enough for us to understand whether the navigator will be rebuilt

My submission during the contest :72160563

while(!q.empty()) {
        auto v = q.front();
        q.pop();
        for (auto u : gt[v]) {
            if (d[u] == d[v] + 1) {
                counter[u]++;
            }
            if (d[u] == 1e9) {
                d[u] = d[v] + 1;
                q.push(u);
            }
        }
    }
→ Reply