man wnlp (Fonctions bibliothèques) - 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