Function Repository Resource:

# FindLongestPath

Find the longest path between two vertices in a directed acyclic graph

Contributed by: Charles Pooh
 ResourceFunction["FindLongestPath"][g,s,t] finds the longest path from source vertex s to target vertex t in the directed acyclic graph g. ResourceFunction["FindLongestPath"][{v→w,…},…] uses rules v→w to specify the graph g.

## Details and Options

ResourceFunction["FindLongestPath"][g,s,t] gives a path from s to t.
ResourceFunction["FindLongestPath"] can only be used for directed acyclic graphs (DAGs).
ResourceFunction["FindLongestPath"] uses the Bellman–Ford algorithm on a DAG with negative weights.

## Examples

### Basic Examples (2)

Find the longest path from the root of a directed acyclic graph (DAG) to a leaf:

 In[1]:=
 In[2]:=
 Out[2]=

Highlight the longest path:

 In[3]:=
 Out[3]=

### Scope (2)

FindLongestPath works with directed acyclic graphs:

 In[4]:=
 In[5]:=
 Out[5]=

Use rules to specify the graph:

 In[6]:=
 In[7]:=
 Out[7]=
 In[8]:=
 Out[8]=

### Possible Issues (1)

FindLongestPath is left unevaluated if the input graph is not a DAG:

 In[9]:=
 Out[9]=

## Version History

• 1.0.0 – 18 December 2020