Peregrine_Falcon's blog

How to find the number of all possible paths in a undirected graph?
By Peregrine_Falcon, history, 6 years ago, In English

I've a graph consisting of 22 nodes and 36 edges. It's an undirected graph. From each node, I've to find the number of ways that I can reach all other nodes. Any idea please?

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

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

What are the rules here? Can you use one edge or vertex multiple times?

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

    Yes. But in a path I can't use a cycle. Cause it'll give me a infinite answer. Two paths will consider different, if at least 1 edge deffer.

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

    Sorry I was sleeping when I replied to your comment. So, I messed Up. In a path I cant use a edge multiple times. It will create a cycle. For graph -

    1 — 2

    2 — 4

    2 — 3

    4 — 3

    3 — 5

    If we consider the source 1 and target 5 output will be 2 for that. Like that from every node to all other node I've to find the number of ways. I don't have any time limit. I can run the code for few hours. I just need the output. Thank You.

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

      Since you only require the result and the graph is very small (and sparse), have you considered using brute force?

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

        I was busy for few days, I ran brute force for this. Got my result.

        Thank You.

        → Reply