1
$\begingroup$

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.

graph

Improve this question
$\endgroup$
1
$\begingroup$

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"]

enter image description here

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

$235$.

Here are just 12 of the paths:

enter image description here

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).

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.