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

# wncp(3)

critical path problem

## NAME

wn\_critical\_path - critical path problem

## SYNOPSIS

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

wn_critical_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 "critical path" problem easily and efficiently.  *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.  *length\_mat* must be a DAG; it must contain no cycles or undirected edges.  *result* is the list of edges in the critical path, ordered starting from *start\_node*. *len* is set to the total length of the solution.

The critical 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.

Difficult optimization problems from many fields can be put into this form, and thus solved efficiently with this package.

For an introduction to the critical path problem, consult \[1\].

## RESOURCES

Solving a critical path problem requires

AVERAGE CASE:

time = e stack memory = 1 dynamic memory = n

WORST CASE:

time = e 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).

## DIAGNOSTICS

*code* == WN\_SUCCESS  for successful solution. *code* == WN\_INFEASIBLE if no path from *start\_node* to *fin\_node* exists, or if the graph contains cycles or undirected edges.

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

## SEE ALSO

wnsp, wnlp, wnsplx

## AUTHOR

Will Naylor