naginterfaces.library.mip.shortestpath

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

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://support.nag.com/numeric/nl/nagdoc_30.1/flhtml/h/h03adf.html

Parameters

nint

$n$, the number of vertices.

nsint

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

neint

$n_s$ and $n_e$, 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.

$direct=True$

The network is directed.

$direct=False$

The network is undirected.

dfloat, array-like, shape $\left(\text{nnz}\right)$

The nonzero elements of the distance matrix $D$, ordered by increasing row index and increasing column index within each row. More precisely, $d\left[k\right]$ must contain the value of the nonzero element with indices ($irow\left[k\right],icol\left[k\right]$); this is the length of the arc from the vertex with label $irow\left[k\right]$ to the vertex with label $icol\left[k\right]$. Elements with the same row and column indices are not allowed. If $direct=False$, then only those nonzero elements in the strict upper triangle of $d$ need be supplied since $d_{ij}=d_{ji}$. (sparse.real_gen_sort may be used to sort the elements of an arbitrarily ordered matrix into the required form.)

irowint, array-like, shape $\left(\text{nnz}\right)$

$irow\left[k\right]$ and $icol\left[k\right]$ must contain the row and column indices, respectively, for the nonzero element stored in $d\left[k\right]$.

icolint, array-like, shape $\left(\text{nnz}\right)$

$irow\left[k\right]$ and $icol\left[k\right]$ must contain the row and column indices, respectively, for the nonzero element stored in $d\left[k\right]$.

Returns

splenfloat

The length of the shortest path between the specified vertices $n_s$ and $n_e$.

pathint, ndarray, shape $\left(n\right)$

Contains details of the shortest path between the specified vertices $n_s$ and $n_e$. More precisely, $ns=path\left[0\right]\to path\left[1\right]\to \cdots \to path\left[p\right]=ne$ for some $p\le n$. The remaining $(n-p)$ elements are set to zero.

Raises

NagValueError

(errno $1$)

On entry, $ns=⟨value⟩$ and $ne=⟨value⟩$.

Constraint: $ns\ne ne$.

(errno $1$)

On entry, $ne=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le ne\le n$.

(errno $1$)

On entry, $ns=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le ns\le n$.

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 2$.

(errno $2$)

On entry, $\text{nnz}=⟨value⟩$ and $n=⟨value⟩$.

Constraint: if $direct=False$, $1\le \text{nnz}\le n\times (n-1)/2$.

(errno $2$)

On entry, $\text{nnz}=⟨value⟩$ and $n=⟨value⟩$.

Constraint: if $direct=True$, $1\le \text{nnz}\le n\times (n-1)$.

(errno $3$)

On entry, $k=⟨value⟩$, $irow[k-1]=⟨value⟩$, $icol[k-1]=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le irow[k-1]\le n$, $1\le icol[k-1]\le n$; $icol[k-1]\ne irow[k-1]$ when $direct=True$.

(errno $4$)

On entry, $k=⟨value⟩$, $irow[k-1]=⟨value⟩$, $icol[k-1]=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $1\le irow[k-1]<icol[k-1]\le n$ when $direct=False$.

(errno $5$)

On entry, $k=⟨value⟩$, $d[k-1]=⟨value⟩$.

Constraint: $d[k-1]>0.0$.

(errno $6$)

On entry, $k=⟨value⟩$, $irow[k-1]=⟨value⟩$, $irow[k-2]=⟨value⟩$, $icol[k-1]=⟨value⟩$, $icol[k-2]=⟨value⟩$.

Constraints: $irow[k-2]<irow[k-1]$ or $irow[k-2]=irow[k-1]$ and $icol[k-2]<icol[k-1]$.

(errno $7$)

On entry, $k=⟨value⟩$ $irow[k-1]=⟨value⟩$, $irow[k-2]=⟨value⟩$ $icol[k-1]=⟨value⟩$, $icol[k-2]=⟨value⟩$.

Constraint: $irow[k-1]\ne irow[k-2]$ or $icol[k-1]\ne icol[k-2]$.

(errno $8$)

On entry, $ns=⟨value⟩$ and $ne=⟨value⟩$.

No connected network exists between vertices $ns$ and $ne$.

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 $i$ and whose destination vertex is $j$ can be written as $i\to j$. In an undirected network the arcs $i\to j$ and $j\to i$ are equivalent (i.e., $i\leftrightarrow j$), 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 $n$ vertices which are labelled by the integers $1,2,\dots ,n$. The lengths of the arcs between the vertices are defined by the $n\times n$ distance matrix $d$, in which the element $d_{ij}$ gives the length of the arc $i\to j$; $d_{ij}=0$ if there is no arc connecting vertices $i$ and $j$ (as is the case for an acyclic network when $i=j$). Thus the matrix $D$ is usually sparse. For example, if $n=4$ and the network is directed, then

$$\begin{array}{c}d=\left(\begin{array}{cccc}0& d_{12}& d_{13}& d_{14}\\ d_{21}& 0& d_{23}& d_{24}\\ d_{31}& d_{32}& 0& d_{34}\\ d_{41}& d_{42}& d_{43}& 0\end{array}\right)\text{.}\end{array}$$

If the network is undirected, $d$ is symmetric since $d_{ij}=d_{ji}$ (i.e., the length of the arc $i\to j\equiv$ the length of the arc $j\to i$).

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