NAG FL Interface
h03adf (shortestpath)
1
Purpose
h03adf finds the shortest path through a directed or undirected acyclic network using Dijkstra's algorithm.
2
Specification
Fortran Interface
Subroutine h03adf ( |
n, ns, ne, direct, nnz, d, irow, icol, splen, path, iwork, work, ifail) |
Integer, Intent (In) |
:: |
n, ns, ne, nnz, icol(nnz) |
Integer, Intent (Inout) |
:: |
irow(nnz), ifail |
Integer, Intent (Out) |
:: |
path(n), iwork(3*n+1) |
Real (Kind=nag_wp), Intent (In) |
:: |
d(nnz) |
Real (Kind=nag_wp), Intent (Out) |
:: |
splen, work(2*n) |
Logical, Intent (In) |
:: |
direct |
|
C Header Interface
#include <nag.h>
void |
h03adf_ (const Integer *n, const Integer *ns, const Integer *ne, const logical *direct, const Integer *nnz, const double d[], Integer irow[], const Integer icol[], double *splen, Integer path[], Integer iwork[], double work[], Integer *ifail) |
|
C++ Header Interface
#include <nag.h> extern "C" {
void |
h03adf_ (const Integer &n, const Integer &ns, const Integer &ne, const logical &direct, const Integer &nnz, const double d[], Integer irow[], const Integer icol[], double &splen, Integer path[], Integer iwork[], double work[], Integer &ifail) |
}
|
The routine may be called by the names h03adf or nagf_mip_shortestpath.
3
Description
h03adf 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
by
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
h03adf is described in detail in
Section 9.
4
References
Dijkstra E W (1959) A note on two problems in connection with graphs Numer. Math. 1 269–271
5
Arguments
-
1:
– Integer
Input
-
On entry: , the number of vertices.
Constraint:
.
-
2:
– Integer
Input
-
3:
– Integer
Input
-
On entry: and , the labels of the first and last vertices, respectively, between which the shortest path is sought.
-
4:
– Logical
Input
-
On entry: indicates whether the network is directed or undirected.
- The network is directed.
- The network is undirected.
-
5:
– Integer
Input
-
On entry: the number of nonzero elements in the distance matrix .
Constraints:
- if , ;
- if , .
-
6:
– Real (Kind=nag_wp) array
Input
-
On entry: 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
. (
f11zaf may be used to sort the elements of an arbitrarily ordered matrix into the required form. This is illustrated in
Section 10.)
Constraint:
, for .
-
7:
– Integer array
Input
-
8:
– Integer array
Input
-
On entry: and must contain the row and column indices, respectively, for the nonzero element stored in .
Constraints:
irow and
icol must satisfy the following constraints (which may be imposed by a call to
f11zaf):
- ;
- and , for .
In addition, if , , and ;
- if , .
-
9:
– Real (Kind=nag_wp)
Output
-
On exit: the length of the shortest path between the specified vertices and .
-
10:
– Integer array
Output
-
On exit: contains details of the shortest path between the specified vertices and . More precisely, for some . The remaining elements are set to zero.
-
11:
– Integer array
Workspace
-
-
12:
– Real (Kind=nag_wp) array
Workspace
-
-
13:
– Integer
Input/Output
-
On entry:
ifail must be set to
,
. If you are unfamiliar with this argument you should refer to
Section 4 in the Introduction to the NAG Library FL Interface for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
is recommended. If the output of error messages is undesirable, then the value
is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
.
When the value is used it is essential to test the value of ifail on exit.
On exit:
unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
or
, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
-
On entry, .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
-
On entry, and .
Constraint: if , .
On entry, and .
Constraint: if , .
-
On entry, , , and .
Constraint: , ; when .
-
On entry, , , and .
Constraint: when .
-
On entry, , .
Constraint: .
-
On entry, , , , , .
Constraints: or and .
-
On entry, , , .
Constraint: or .
-
On entry,
and
.
No connected network exists between vertices
ns and
ne.
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
7
Accuracy
The results are exact, except for the obvious rounding errors in summing the distances in the length of the shortest path.
8
Parallelism and Performance
h03adf is not threaded in any implementation.
h03adf is based upon Dijkstra's algorithm (see
Dijkstra (1959)), which attempts to find a path
between two specified vertices
and
of shortest length
.
The algorithm proceeds by assigning labels to each vertex, which may be temporary or permanent. A temporary label can be changed, whereas a permanent one cannot. For example, if vertex has a permanent label , then is the distance and is the previous vertex on a shortest length path. If the label is temporary, then it has the same meaning but it refers only to the shortest path found so far. A shorter one may be found later, in which case the label may become permanent.
The algorithm consists of the following steps.
-
1.Assign the permanent label to vertex and temporary labels to every other vertex. Set and go to 2.
-
2.Consider each vertex adjacent to vertex with a temporary label in turn. Let the label at be and at . If , then a new temporary label is assigned to vertex ; otherwise no change is made in the label of . When all vertices with temporary labels adjacent to have been considered, go to 3.
-
3.From the set of temporary labels, select the one with the smallest second component and declare that label to be permanent. The vertex it is attached to becomes the new vertex . If go to 4. Otherwise go to 2 unless no new vertex can be found (e.g., when the set of temporary labels is ‘empty’ but , in which case no connected network exists between vertices and ).
-
4.To find the shortest path, let denote the label of vertex . The column label () gives while the row label () then links back to the previous vertex on a shortest length path. Go to vertex . Suppose that the (permanent) label of vertex is , then the next previous vertex is on a shortest length path. This process continues until vertex is reached. Hence the shortest path is
which has length .
10
Example
This example finds the shortest path between vertices
and
for the undirected network
10.1
Program Text
10.2
Program Data
10.3
Program Results