wn_longest_path3
Longest path problem
Part of wnlp(3).
Usage
int code;
double len;
wn_sll result;
/*
list
of
edges
*/
wn_sparse_matrix length_mat;
int start_node,fin_node;
Overview
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.
References
[1] Garey & Johnson