wnlp(3)

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 us

ing 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 undi

rected 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 num

ber 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 gen

eral 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

WNLIB August 23, 1998

WNLP(3)