hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_mip_shortestpath (h03ad)

Purpose

nag_mip_shortestpath (h03ad) finds the shortest path through a directed or undirected acyclic network using Dijkstra's algorithm.

Syntax

[splen, path, ifail] = h03ad(n, ns, ne, direct, d, irow, icol, 'nnz', nnz)
[splen, path, ifail] = nag_mip_shortestpath(n, ns, ne, direct, d, irow, icol, 'nnz', nnz)

Description

nag_mip_shortestpath (h03ad) 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 ii and whose destination vertex is jj can be written as ijij. In an undirected network the arcs ijij and jiji are equivalent (i.e., ijij), 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 nn vertices which are labelled by the integers 1,2,,n1,2,,n. The lengths of the arcs between the vertices are defined by the nn by nn distance matrix dd, in which the element dijdij gives the length of the arc ijij; dij = 0dij=0 if there is no arc connecting vertices ii and jj (as is the case for an acyclic network when i = ji=j). Thus the matrix DD is usually sparse. For example, if n = 4n=4 and the network is directed, then
d =
  0 d12 d13 d14 d21 0 d23 d24 d31 d32 0 d34 d41 d42 d43 0  
.
d= 0 d12 d13 d14 d21 0 d23 d24 d31 d32 0 d34 d41 d42 d43 0 .
If the network is undirected, dd is symmetric since dij = djidij=dji (i.e., the length of the arc ijij the length of the arc jiji).
The method used by nag_mip_shortestpath (h03ad) is described in detail in Section [Further Comments].

References

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

Parameters

Compulsory Input Parameters

1:     n – int64int32nag_int scalar
nn, the number of vertices.
Constraint: n2n2.
2:     ns – int64int32nag_int scalar
3:     ne – int64int32nag_int scalar
nsns and nene, the labels of the first and last vertices, respectively, between which the shortest path is sought.
Constraints:
  • 1nsn1nsn;
  • 1nen1nen;
  • nsnensne.
4:     direct – logical scalar
Indicates whether the network is directed or undirected.
direct = truedirect=true
The network is directed.
direct = falsedirect=false
The network is undirected.
5:     d(nnz) – double array
nnz, the dimension of the array, must satisfy the constraint
  • if direct = truedirect=true, 1nnzn × (n1)1nnzn×(n-1);
  • if direct = falsedirect=false, 1nnzn × (n1) / 21nnzn×(n-1)/2.
The nonzero elements of the distance matrix DD, ordered by increasing row index and increasing column index within each row. More precisely, d(k)dk must contain the value of the nonzero element with indices (irow(k),icol(k)irowk,icolk); this is the length of the arc from the vertex with label irow(k)irowk to the vertex with label icol(k)icolk. Elements with the same row and column indices are not allowed. If direct = falsedirect=false, then only those nonzero elements in the strict upper triangle of dd need be supplied since dij = djidij=dji. (nag_sparse_real_gen_sort (f11za) may be used to sort the elements of an arbitrarily ordered matrix into the required form. This is illustrated in Section [Example].)
Constraint: d(k) > 0.0dk>0.0, for k = 1,2,,nnzk=1,2,,nnz.
6:     irow(nnz) – int64int32nag_int array
7:     icol(nnz) – int64int32nag_int array
nnz, the dimension of the array, must satisfy the constraint
  • if direct = truedirect=true, 1nnzn × (n1)1nnzn×(n-1);
  • if direct = falsedirect=false, 1nnzn × (n1) / 21nnzn×(n-1)/2.
irow(k)irowk and icol(k)icolk must contain the row and column indices, respectively, for the nonzero element stored in d(k)dk.
Constraints:
irow and icol must satisfy the following constraints (which may be imposed by a call to nag_sparse_real_gen_sort (f11za)):
  • irow(k1) < irow(k)irowk-1<irowk;
  • irow(k1) = irow(k)irowk-1=irowk and icol(k1) < icol(k)icolk-1<icolk, for k = 2,3,,nnzk=2,3,,nnz.
In addition, if direct = truedirect=true, 1irow(k)n1irowkn, 1icol(k)n1icolkn and irow(k)icol(k)irowkicolk;
  • if direct = falsedirect=false, 1irow(k) < icol(k)n1irowk<icolkn.

Optional Input Parameters

1:     nnz – int64int32nag_int scalar
Default: The dimension of the arrays irow, icol, d. (An error is raised if these dimensions are not equal.)
The number of nonzero elements in the distance matrix DD.
Constraints:
  • if direct = truedirect=true, 1nnzn × (n1)1nnzn×(n-1);
  • if direct = falsedirect=false, 1nnzn × (n1) / 21nnzn×(n-1)/2.

Input Parameters Omitted from the MATLAB Interface

iwork work

Output Parameters

1:     splen – double scalar
The length of the shortest path between the specified vertices nsns and nene.
2:     path(n) – int64int32nag_int array
Contains details of the shortest path between the specified vertices nsns and nene. More precisely, ns = path(1)path(2)path(p) = nens=path1path2pathp=ne for some pnpn. The remaining (np)(n-p) elements are set to zero.
3:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
On entry,n < 2n<2,
orns < 1ns<1,
orns > nns>n,
orne < 1ne<1,
orne > nne>n,
orns = nens=ne.
  ifail = 2ifail=2
On entry,nnz > n × (n1)nnz>n×(n-1) when direct = truedirect=true,
ornnz > n × (n1) / 2nnz>n×(n-1)/2 when direct = falsedirect=false,
ornnz < 1nnz<1.
  ifail = 3ifail=3
On entry, irow(k) < 1irowk<1 or irow(k) > nirowk>n or icol(k) < 1icolk<1 or icol(k) > nicolk>n or irow(k) = icol(k)irowk=icolk for some kk when direct = truedirect=true.
  ifail = 4ifail=4
On entry, irow(k) < 1irowk<1 or irow(k)icol(k)irowkicolk or icol(k) > nicolk>n for some kk when direct = falsedirect=false.
  ifail = 5ifail=5
d(k)0.0dk0.0 for some kk.
  ifail = 6ifail=6
On entry, irow(k1) > irow(k)irowk-1>irowk or irow(k1) = irow(k)irowk-1=irowk and icol(k1) > icol(k)icolk-1>icolk for some kk.
  ifail = 7ifail=7
On entry, irow(k1) = irow(k)irowk-1=irowk and icol(k1) = icol(k)icolk-1=icolk for some kk.
  ifail = 8ifail=8
No connected network exists between vertices ns and ne.

Accuracy

The results are exact, except for the obvious rounding errors in summing the distances in the length of the shortest path.

Further Comments

nag_mip_shortestpath (h03ad) is based upon Dijkstra's algorithm (see Dijkstra (1959)), which attempts to find a path nsnensne between two specified vertices nsns and nene of shortest length d(ns,ne)d(ns,ne).
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 pp has a permanent label (q,r)(q,r), then rr is the distance d(ns,r)d(ns,r) and qq is the previous vertex on a shortest length nspnsp path. If the label is temporary, then it has the same meaning but it refers only to the shortest nspnsp 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 (,0)(-,0) to vertex nsns and temporary labels (,)(-,) to every other vertex. Set k = nsk=ns and go to 2..
  2. Consider each vertex yy adjacent to vertex kk with a temporary label in turn. Let the label at kk be (p,q)(p,q) and at y(r,s)y(r,s). If q + dky < sq+dky<s, then a new temporary label (k,q + dky)(k,q+dky) is assigned to vertex yy; otherwise no change is made in the label of yy. When all vertices yy with temporary labels adjacent to kk 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 kk. If k = nek=ne 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 knekne, in which case no connected network exists between vertices nsns and nene).
  4. To find the shortest path, let (y,z)(y,z) denote the label of vertex nene. The column label (zz) gives d(ns,ne)d(ns,ne) while the row label (yy) then links back to the previous vertex on a shortest length nsnensne path. Go to vertex yy. Suppose that the (permanent) label of vertex yy is (w,x)(w,x), then the next previous vertex is ww on a shortest length nsynsy path. This process continues until vertex nsns is reached. Hence the shortest path is
    nswyne,
    nswyne,
    which has length d(ns,ne)d(ns,ne).

Example

function nag_mip_shortestpath_example
n = int64(11);
ns = int64(1);
ne = int64(11);
direct = false;
d = [5;
     6;
     5;
     2;
     4;
     1;
     4;
     1;
     3;
     1;
     9;
     1;
     6;
     7;
     8;
     1;
     4;
     2;
     2;
     4];
irow = [int64(1);1;1;2;2;3;3;4;4;5;5;6;6;6;7;8;8;9;9;10];
icol = [int64(2);3;4;3;5;4;6;6;7;6;9;7;8;10;9;9;11;10;11;11];
[splen, path, ifail] = nag_mip_shortestpath(n, ns, ne, direct, d, irow, icol)
 

splen =

    15


path =

                    1
                    4
                    6
                    8
                    9
                   11
                    0
                    0
                    0
                    0
                    0


ifail =

                    0


function h03ad_example
n = int64(11);
ns = int64(1);
ne = int64(11);
direct = false;
d = [5;
     6;
     5;
     2;
     4;
     1;
     4;
     1;
     3;
     1;
     9;
     1;
     6;
     7;
     8;
     1;
     4;
     2;
     2;
     4];
irow = [int64(1);1;1;2;2;3;3;4;4;5;5;6;6;6;7;8;8;9;9;10];
icol = [int64(2);3;4;3;5;4;6;6;7;6;9;7;8;10;9;9;11;10;11;11];
[splen, path, ifail] = h03ad(n, ns, ne, direct, d, irow, icol)
 

splen =

    15


path =

                    1
                    4
                    6
                    8
                    9
                   11
                    0
                    0
                    0
                    0
                    0


ifail =

                    0



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013