naginterfaces.library.mip.shortestpath

naginterfaces.library.mip.shortestpath(n, ns, ne, direct, d, irow, icol)[source]

shortestpath finds the shortest path through a directed or undirected acyclic network using Dijkstra’s algorithm.

For full information please refer to the NAG Library document for h03ad

https://www.nag.com/numeric/nl/nagdoc_28.5/flhtml/h/h03adf.html

Parameters
nint

, the number of vertices.

nsint

and , the labels of the first and last vertices, respectively, between which the shortest path is sought.

neint

and , the labels of the first and last vertices, respectively, between which the shortest path is sought.

directbool

Indicates whether the network is directed or undirected.

The network is directed.

The network is undirected.

dfloat, array-like, shape

The nonzero elements of the distance matrix , ordered by increasing row index and increasing column index within each row. More precisely, must contain the value of the nonzero element with indices (); this is the length of the arc from the vertex with label to the vertex with label . Elements with the same row and column indices are not allowed. If , then only those nonzero elements in the strict upper triangle of need be supplied since . (sparse.real_gen_sort may be used to sort the elements of an arbitrarily ordered matrix into the required form.)

irowint, array-like, shape

and must contain the row and column indices, respectively, for the nonzero element stored in .

icolint, array-like, shape

and must contain the row and column indices, respectively, for the nonzero element stored in .

Returns
splenfloat

The length of the shortest path between the specified vertices and .

pathint, ndarray, shape

Contains details of the shortest path between the specified vertices and . More precisely, for some . The remaining elements are set to zero.

Raises
NagValueError
(errno )

On entry, and .

Constraint: .

(errno )

On entry, and .

Constraint: .

(errno )

On entry, and .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, and .

Constraint: if , .

(errno )

On entry, and .

Constraint: if , .

(errno )

On entry, , , and .

Constraint: , ; when .

(errno )

On entry, , , and .

Constraint: when .

(errno )

On entry, , .

Constraint: .

(errno )

On entry, , , , , .

Constraints: or and .

(errno )

On entry, , , .

Constraint: or .

(errno )

On entry, and .

No connected network exists between vertices and .

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

shortestpath attempts to find the shortest path through a directed or undirected acyclic network, which consists of a set of points called vertices and a set of curves called arcs that connect certain pairs of distinct vertices. An acyclic network is one in which there are no paths connecting a vertex to itself. An arc whose origin vertex is and whose destination vertex is can be written as . In an undirected network the arcs and are equivalent (i.e., ), whereas in a directed network they are different. Note that the shortest path may not be unique and in some cases may not even exist (e.g., if the network is disconnected).

The network is assumed to consist of vertices which are labelled by the integers . The lengths of the arcs between the vertices are defined by the distance matrix , in which the element gives the length of the arc ; if there is no arc connecting vertices and (as is the case for an acyclic network when ). Thus the matrix is usually sparse. For example, if and the network is directed, then

If the network is undirected, is symmetric since (i.e., the length of the arc the length of the arc ).

The method used by shortestpath is described in detail in Further Comments.

References

Dijkstra, E W, 1959, A note on two problems in connection with graphs, Numer. Math. (1), 269–271