noobKunal's blog

Count of simple paths from source to destination via some node.
By noobKunal, 3 years ago, In English

Undirected unweighted connected graph is given (no self loops or multiple edges). We have to calculate for each node x number of simple paths with minimum distance from node 1 to node N passing through that node x.

Constraints: N <= 1e3 Number of edges, M <= N * (N-1) / 2 I tried the following approach:

let count(i, j) = count of shortest paths from i to j so required count for any node x = count(1, x) * count(x, n)

but i got stuck tc: N = 5 edges: 1 2
1 3
1 4
2 4
2 5

expected o/p = 1 1 0 1 1
In this test case my mentioned formula clearly fails for x = 3 as we have to repeat edge 1-3 for going from node 1 to 5 via node 3.

How can i handle such cases of repetetions?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give link to the problem ? ( Just to confirm that it's not from ongoing contest)

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

    I don't have link as this problem appeared recently in company coding round (Juspay)

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

      I think it could be solved using simple BFS . Just run a BFS from node N and count the ways for each node.

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

        I was trying to use BFS only but it won't work in case of repetetions.

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

How did you evaluate count(i,j) in O(n)?

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

    Sorry i must've mentioned it, for each node i, I am only calculating : count (1, i) and count(i, N). That we can find in O(N) using simple BFS.

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

How the answer for node 4 equals 1? Shouldn't it be 0 since minimum distance from 1 to 5 is 2 and when we pass through 4, distance will be 3.

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

    I think you misinterpreted the question. For each node x, we have to find the number of shortest paths which must include x. So, the shortest path from 1 to 5 which includes 4 is 1->4->2->5.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your approach works, you just need to convert the graph into a DAG first.

Notice that for all shortest simple paths from 1 to N and a particular edge v-w, this edge is only used in one direction in all of them.

Proof: if there was a shortest path of length D: 1->{A}->v->w->{B}->N, and also one 1->{X}->w->v->{Y}->N (for some simple paths {A},{B},{X},{Y}), then the two paths 1->{A}->v->{Y}->N, 1->{X}->w->{B}->N have 2 fewer edges (w->v and v->w), so the sum of their lengths < 2*D, so one of them would have to be shorter than D, a contradiction).

How to convert graph to DAG: BFS from node 1 to node N, finding the shortest distance from node 1 to each node. Then BFS (backtrack) from node N, like so:

(v belongs to some shortest path from 1->N)
if I am in node v, looking at an edge v<->w:
  if w.dist == v.dist - 1:
    w belongs to a shortest path from 1 to N; add w to queue if it isnt already,
    and add the edge v->w to my DAG graph

Then running your approach on the DAG should work.

It sounds like it would be $$$O(NM)$$$ = $$$O(N^3)$$$ though, I feel like it could be possible to do better?

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

    Consider case N = 5 and edges:
    1-2
    1-3
    2-5
    3-4
    4-5
    What will be your DAG in this case and your final answer for x = 4?

    → Reply