Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Peregrine_Falcon's blog

How to find the number of all possible paths in a undirected graph?
By Peregrine_Falcon, history, 7 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

»
7 years ago, hide # |
 
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
  • »
    »
    7 years ago, hide # ^ |
     
    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
  • »
    »
    7 years ago, hide # ^ |
    ← 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