---
name: "wnlp"
section: "3"
platform: "linux"
package: "libwn-dev"
version: "6.0-17"
release: "Debian 4.0 (Etch)"
platforms: ["linux"]
url: "https://new.carta.tech/wnlp"
---

# wnlp(3)

longest path problem

## NAME

wn\_longest\_path - longest path problem

## SYNOPSIS

```
#include <wn/wnspmat.h>
#include <wn/wnlp.h>

wn_longest_path(&code,&len,&result,length_mat,start_node,fin_node)
int code;
double len;
wn_sll result; /* list of edges */
wn_sparse_matrix length_mat;
int start_node,fin_node;
```

## DESCRIPTION

This package solves the "longest path" problem easily  using exponential search.  *length\_mat* is treated as a DIRECTED GRAPH; thus it must be square.  The matrix entry *length\_mat*\[i\]\[j\] gives the length of the directed edge from node i to node j.  Negative edge lengths are allowed.  *result* is the list of edges in the longest path, ordered starting from *start\_node*. *len* is set to the total length of the solution.

The longest path problem is the following optimization problem:

Choose the path in the graph *length\_mat* from *start\_node* to *fin\_node* which is the longest possible path.

If the graph is DAG (that is, it lacks cycles and undirected edges), it can be solved more efficiently using wncp.

## RESOURCES

Solving a longest path problem requires

WORST and AVERAGE CASE:

time = n^(e/n)\
 stack memory = n\
 dynamic memory = n

where e is the number of matrix entries, and n is the number of nodes in the graph represented by *length\_mat*.  (n == len\_i == len\_j).

Note:  the longest path problem is NP-complete \[1\], and thus no algorithms faster than exponential are known for the general problem.

## DIAGNOSTICS

*code* == WN\_SUCCESS  for successful solution. *code* == WN\_INFEASIBLE if no path from *start\_node* to *fin\_node* exists.

len\_i != len\_j causes a crash.

## SEE ALSO

wncp, wnsp, wnsplx, wnmst

## REFERENCES

\[1\]  Garey & Johnson

## AUTHOR

Will Naylor