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

# wnsp(3)

shortest path problem

## NAME

wn\_shortest\_path - shortest path problem

## SYNOPSIS

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

wn_shortest_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 "shortest path" problem easily and efficiently using Dijkstra's algorithm \[1\].  *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 not allowed.  *result* is the list of edges in the shortest path, ordered starting from *start\_node*. *len* is set to the total length of the solution.

The shortest path problem is the following optimization problem:

Choose the path in the graph *length\_mat* from *start\_node* to *fin\_node* which is the shortest 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 shortest path problem, consult \[1\].

## RESOURCES

Solving a shortest path problem requires

WORST CASE:

time = e+n\*log(n)\
 stack memory = 1\
 dynamic memory = n

AVERAGE CASE:

time = depends heavily on problem structure stack memory = 1 dynamic memory = depends heavily on problem structure

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).

If the shortest path involves only a small fraction of the graph nodes, run time and memory usage are usually very much better than  the worst case.

Note:  the shortest path problem becomes NP-complete if negative edges are allowed \[2\].

## 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.\
 negative edge lengths cause a crash.

## SEE ALSO

wncp, wnlp, wnsplx, wnmst

## REFERENCES

\[1\]  A. Aho, J. Hopcroft, and J. Ullman:  Data Stuctures and  Algorithms.  Addison-Wesley Publishing.

## AUTHOR

Will Naylor