tatya_bichu's blog

How do I find number of distinct paths between any two nodes in graph?
By tatya_bichu, 7 years ago, In English

Given n (no. of vertices) and edges in the undirected graph . For each pair of vertices(say 'u', 'v') find(no need to output these) the number of distinct paths connecting these vertices('u','v') and output the minimum of these.(2<=n<=1500) required O(n^2) solution.

My approach:

1) Make the adjacency matrix and call it A.

2) find matrix B=A+A^2+A^3+...+A^n.(Proof

3) B contains the answer and find minimum of its entries.

But I am unable to do step 2 efficiently .

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

»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

What exactly do you mean by "distinct paths"? Are these paths required to be simple? If no, then for some graphs the answer is infinity and your matrix approach does not work (it may only yield finite answers). If yes, then your matrix approach still does not work as matrix exponentiation does not make all vertexes in the path different.

Maybe you want to find some kind of edge connectivity?

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

    Yes,simple paths only, I think, Original problem is :Problem Is there any simpler method other than finding connectivity or some other simpler method?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      That problem is asking about edge-connectivity exactly: what is the minimal number of edges to destroy so the graph becomes disjoint. It's more or less the same as asking for minimal cut. Wikipedia suggests Karger's algorithm and more general Stoer-Wagner algorithm. If tests are good, looks like the former won't pass, and the latter would with ease.

      Your definition is looks like an application of Menger's theorem, if you add the word "disjoint" there (and if you don't, it's something different, not sure of "minimal number of paths" is still the same).

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

For the problem you are referring to I'd suggest reading about max-flow in graphs.

But as you already asked let's see how we can efficiently implement your step 2. The problem is to find sum A1 + A2 + A3 + ... + AN for A being adjacency matrix. Now let's say that N = 2k (If it's not we manually calculate the last power and add it to the rest). We can transform original sum into

A1 + A2 + A3 + ... + A2k = (A1 + A2 + ... + Ak) + (Ak + 1 + Ak + 2 + ... + A2k)

and by transforming this into

(A1 + A2 + ... + Ak) + (Ak + 1 + Ak + 2 + ... + A2k) = (1 + Ak)(A1 + A2 + ... + Ak)

we halve the number of powers we need to calculate. We now just need to recursively calculate (A1 + A2 + ... + Ak) the same way we did the original sum. Complexity is O(N3 × log2 N). That's the fastest way I know if you are interested in paths from specific nodes. Not connected to your problem in any way but I think it's a pretty neat trick.

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

    yeah,but but that complexity wouldn't be good enough,that's why I asked it here.Thanks for that.

    → Reply