1
$\begingroup$

I want the most efficient algorithm for this problem .

I only want to count all simple paths between the following nodes : - [1,2],[1,3]......[1,n] .

Finally, I want to add them all .

(None of the path should have repeated nodes/cycle(s) )

Constraints : -

1) Every node may only be connected to at most 4 other node(s) which are strictly adjacent, the 'i-th' node will only be connected to either i+1,i+2,i-1,i-2 numbered node in the graph.

2)Graph can contain cycles .

What is the best time complexity I can achieve for this problem?

Example : - 4 nodes , 6 edges : -

(1,2)

(2,1)

(2,4)

(2,3)

(3,4)

(3,2)

(4,3)

Output : - [1,1] + [1,2] + [1,3] + [1,4] = 1 + 1 + 2 + 2 = 6 :)

$\endgroup$

put on hold as off-topic by user21820, RRL, YuiTo Cheng, José Carlos Santos, Jendrik Stelzner Jun 13 at 12:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, RRL, YuiTo Cheng, José Carlos Santos, Jendrik Stelzner
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ A suspected contest cheater. People in CRUDE are digging up more. $\endgroup$ – Jyrki Lahtonen 2 days ago

Browse other questions tagged or ask your own question.