wnsp(3)

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 treat

ed 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 pack

age.

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 num

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

ter 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

WNLIB August 23, 1998

WNSP(3)