# Determine number of possible paths in an undirected graph [closed]

I have a graph consisting of a start point $$S$$, a finish point $$F$$ and a number of intermediate points $$P_i$$. The points are connected by a set of edges, as shown in the graph below. I need to determine the number of unique paths connecting the start to the finish. The rules:

• The number of points per path is not fixed
• Each path can pass by a point one time only (to avoid loops)

I'm a graph theory noob and I'm sure this is a quite common problem. Do you have suggestions to where should I look to get an introduction to the problem, and suggestions on how to solve it? Ideally, I'm looking for an equation or numerical procedure.

Given that in general this is a hard problem, this seems to be a case where off-the-shelf software can be of use.

In Mathematica:

g = Graph[
{s <-> p1, s <-> p2, p1 <-> p3, p1 <-> p4, s <-> p3, p2 <-> p3,
p2 <-> p5, p2 <-> p6, p3 <-> p4, p4 <-> p5, p3 <-> p6, p4 <-> p7,
p5 <-> p6,p3 <-> p5, p5 <-> p7, p6 <-> p7,p7 <-> F, p5 <-> F, p6 <-> F},
VertexLabels -> Automatic,
GraphLayout -> "SpringEmbedding"]


numpaths = Length[FindPath[g, s, F, Infinity, All]]


$$235$$.

Here are just 12 of the paths:

As for sources of information on this problem, I'd recommend (for a newbie) A first course in Graph Theory by Chartrand and Zhang (Dover).

For posterity: another possible approach is to use the function shortest_simple_paths from NetworkX. As a reference, see here.