STATES IMENT OF lERCE

NATION

"'Co.

y"

NBS TECHNICAL NOTE 772

A Performance Comparison

of Labeling Algorithms

for Calculating

Shortest Path Trees

U.S.

iRTMENT

OF

MMERCE

National "

"^au ^"^

of

>0 ds

n53

11:1

73
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards^ was established by an act of Congress March 3, 1901. The Bureau's overall goal is to strengthen and advance the Nation's science and

technology and facilitate their effective application for public benefit. To this end, the Bureau conducts research and provides: (1) a basis for the Nation's physical measure- ment system, (2) scientific and technological services for industry and government, (3) a technical basis for equity in trade, and (4) technical services to promote public safety. The Bureau consists of the Institute for Basic Standards, the Institute for Materials Research, the Institute for Applied Technology, the Center for Computer Sciences and

Technology, and the Oflfice for Information Programs.

THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the United States of a complete and consistent system of physical measurement; coordinates

that system with measurement systems of other nations; and furnishes essential services leading to accurate and uniform physical measurements throughout the Nation's scientific community, industry, and commerce. The Institute consists of a Center for Radiation Research, an Office of Measurement Services and the following divisions: Applied Mathematics — Electricity — Mechanics — Heat — Optical Physics —

Linac Radiation - — Nuclear Radiation - — Applied Radiation - — Quantum

Electronics ' — Electromagnetics '• — Time and Frequency ^ — Laboratory

Astrophysics — Cryogenics ''. THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research lead- ing to improved methods of measurement, standards, and data on the properties of

well-characterized materials needed by industry, commerce, educational institutions, and

Government; provides advisory and research services to other Government agencies; and develops, produces, and distributes standard reference materials. The Institute consists of the Office of Standard Reference Materials and the following divisions: Analytical Chemistry—Polymers—Metallurgy—Inorganic Materials—Reactor

Radiation—Physical Chemistry.

THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services to pro- mote the use of available technology and to facilitate technological innovation in industry and Government; cooperates with public and private organizations leading to the development of technological standards (including mandatory safety standards), codes and methods of test; and provides technical advice and services to Government agencies upon request. The Institute also monitors NBS engineering standards activities and

provides liaison between NBS and national and international engineering standards

bodies. The Institute consists of a Center for Building Technology and the following

divisions and offices: Engineering and Product Standards—Weights and Measures—Invention and

Innovation—Product Evaluation Technology—Electronic Technology—^Technical Analysis—Measurement Engineering—Building Standards and Code Services*—Housing Technology*—Federal Building Technology*—Structures, Materials and Life Safety^—Building Environment*—Technical Evaluation and

Application*—Fire Technology.

THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts re- search and provides technical services designed to aid Government agencies in improving cost effectiveness in the conduct of their programs through the selection, acquisition, and effective utilization of automatic data processing equipment; and serves as the principal focus within the executive branch for the development of Federal standards for automatic data processing equipment, techniques, and computer languages. The Center

consists of the following offices and divisions: Information Processing Standards—Computer Information—Computer Services —Systems Development—Information Processing Technology.

THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination and accessibility of scientific information generated within NBS and other agencies of

the Federal Government; promotes the development of the National Standard Reference Data System and a system of information analysis centers dealing with the broader

aspects of the National Measurement System; provides appropriate services to ensure

that the NBS staff has optimum accessibility to the scientific information of the world, and directs the public information activities of the Bureau. The Office consists of the following organizational units: Office of Standard Reference Data—Office of Technical Information and

Publications—Library—Office of International Relations.

1 Headquarters and Laboratories at Gaithersburg, Maryland, unless otherwise noted ; mailing address Washington, D.C. 202.94.

' Part of the Center for Radiation Research.

3 Located at Boulder, Colorado 80302.

* Part of the Center for Building Technology.
SAL £"::[:'•„< n^ sTr;"5as-

^ A Performance Comparison of Labeling Algorithms

;fj for Calculating Shortest Path Trees

'3

Judith Gilsinn

Applied Mathematics Division

Institute for Basic Standards

"H'J' National Bureau of Standards

'•* Washington, D.C. 20234

and

Christoph Witzgall

Boeing Scientific Laboratories

P.O. Box 3999

Seattle, Washington 98124

- NBS-Technical Notes are designed to supplement the Bureau's regular publications program. They provide a means for making available scientific data that are of

transient or limited interest. Technical Notes may be

listed or referred to in the open literature.

..< °>.

U.S. DEPARTMENT OF COMMERCE, Fredericlc B. Dent, SBCTe\Qry

NATIONAL BUREAU OF STANDARDS, Richard W. Roberts, Director

Issued May 1973
National Bureau of Standards Technical Note 772

Nat. Bur. Stand. (U.S.), Tech. Note 772, 92 pages (May 1973) CODEN: NBTNAE

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C. 20402 (Order by SD Catalog No. C13.46:772).

Price $1.25 domestic postpaid or $1.00 G.P.O. Bookstore.
TABLE OF CONTENTS

1Introduction 1

2Network Representation 4

3 Trees 8

4 Basic Labeling Methods 10

5. Techniques to Improve the Label-Correcting Method 12

6. Techniques to Improve the Label-Setting Method 18

7

Experimental Results 23

8Flowchart Conventions 32

9 . Algorithms 37

10References 70

Appendix: FORTRAN Programs for Seven Shortest Path Algorithms 75

LIST OF TABLES

1Results of Comparative Timing Experiments 26

2. Additional Computer Storage Requirements for Shortest Path

Algorithms 30

Xll

A PERPORMANCE COMPARISON OF LABELING ALGORITHMS

FOR CALCULATING SHORTEST PATH TREES

Judith Gllsinn and Christoph Witzgall

Many applications in transportation and

communication require the calculation of shortest

routes between points in a network, and several

algorithms for the solution of this problem exist

in the literature. This paper examines one class

of such algorithms, that which calculates a shortest route from one point in the network to all

other intersection points. Computer data handling

techniques which can be used to improve the two

basic algorithms in this class are investigated.

Results of computer timing runs on various types

and sizes of networks are compared, and the

differences, sometimes of an order of magnitude,

are analyzed. Detailed flowcharts and computer

programs of the tested algorithms are also included.

Key words : Algorithms; networks; paths; shortestpaths; trees.

1. Introduction

In many an analysis of communication and transportation systems,

the problem of finding the shortest, cheapest, or fastest route between

two points arises naturally. One may wish to determine, for instance,

the least cost route to travel by auto between two cities or alternatively the auto route which is fastest. One may want to route a telephone call along telephone lines to minimize the length of the lines over which the call travels.

In other applications, the actual routing is less important than

the numerical value of the minimum time, cost, or distance required.

For instance, one may need to decide which of several warehouses is

closest to his store by rail, in which case he is interested in the rail

distances between his store and the various warehouses rather than the

1
actual routing. One may wish to compare minimiim travel times from suburban areas to the city center by various transportation modes, or to

find the minimum number of relay points which a message has to go

through as it is sent from one point in a communication network to

another.

In all of the examples given above one has a network, which may

consist of road segments, railroad track, other common carrier transportation routes, or direct communication links, and one desires a routing between two points in this network which is minimum according

to some criterion. This problem is usually termed that of finding a shortest path in the network. (The terms "path" and "network" will be

defined more precisely in the next section, but their common understanding is sufficient for the present discussion.)

Often in applications requiring the folding of shortest paths a great many such paths are desired. Typically one wishes to find shortest

paths from all of some subset of network intersections to all of some other (possibly the same) subset of intersections, where "intersections"

can be switching or relay points in a communication network, road

intersections, railroad junction points, airplane terminals, etc. For

many applications the networks are very large, containing many segments

and intersection points, thus requiring the use of a digital computer

for their processing.

A number of algorithms have been developed, and appear in the

literature, for finding shortest paths in such large networks. It is

natural to compare the computational efficiency of the different

k

algorithms on different types of networks. Dreyfus [12] has written

an excellent survey paper classifying the types of algorithms and

giving theoretical computational bounds for each class. Martin [35]

and Hitchner [21] have conducted computational experiments on several

algorithms.

These previous studies, however, have only sketched the actual

computer implementation of the algorithms included, whereas it has been

our experience, confirmed by the results reported in Table 1 of section 7,

* Figures in brackets indicate the literature references on page 71.

2
that the data handling (more specifically, list processing) techniques

employed in programming the algorithms for a digital computer have a

great effect on computation time. Therefore, it is the purpose of this

paper to examine one class of shortest path algorithms, to provide a unified structure for describing and coding them, to give list processing

techniques which can be used to improve the efficiency of the basic

algorithms, and to report the results of computational experiments

utilizing these techniques in such a manner that the exact computer

implementation of the algorithms is known.

This report is directed primarily to the reader who is confronted

with a problem requiring shortest path calculation and who does not have

the time or resources to locate or evaluate available algorithms. Some

familiarity with computers is assumed, but the paper is intended to be

self-contained in terms of network definitions and algorithm descriptions,

Sections 2 and 3 below give the basic definitions and background

relating to the network structures appearing in the algorithms. Section

4 delineates the class of algorithms to be examined in the remainder

of the report and describes the two basic algorithms in this class.

Sections 5 and 6 give list processing techniques which can be used to

improve the efficiency of the basic algorithms . Section 7 includes the

results of the computational experiments and a discussion of the relative

merits of the various techniques. Section 8 describes conventions used

in the flowcharts of the algorithm implementations which are included

in section 9 together with detailed descriptions of the implementations.

The actual programs appear as an appendix.

* Other techniques (not reported here but described in an earlier,

unpublished work by Witzgall) have also been tested, and analyses of

these tests coupled with hindsight have revealed that the techniques

reported in this paper- are the most likely candidates for success.
2. NETWORK REPRESENTATION

In order to give precise descriptions of the shortest path

algorithms, it is first necessary to formalize some definitions. A

network consists of a finite set V of nodes and a finite set E of arcs . To each arc eeE there corresponds an ordered pair (v,w) of nodes,

the starting or beginning node v and the terminating or ending node w,

and we say the arc e leads from v to w . The networks thus defined

are directed networks, since the distinction between the beginning and

ending of an arc imposes a direction on each arc. The term "network"

without modifier will mean directed network throughout this text.

A directed path, or simply path , is a sequence

P = (e ,e ,...,e ) 12 n

of arcs such that for each i = 2,...n, arc e^ begins at the end of arc e . Let v be the beginning of arc e and w the end of

i-1 1 arc e ; then we say the path P starts at v and ends at w , and

n that P is a path from v to w . If a network contains a path from

node V to node w , then w is called accessible from v . If

V = w , i.e. path P starts and ends at the same node, P is called a circuit . A path for which e ?^e whenever i ^ j j i.e. no arc appears

i J in P more than once, is called arc-simple . Assume now that each arc e of a network N has a non-negative

length £(e) associated with it. Then each path P can be assigned a path length

d(P) = Z £(e.) , i=l 1

and we may speak of a shortest path from one particular node to another

as a path P for which d(P) is minimum. Note there may be several

such paths, all having the same (minimum) length; the algorithms

described below only find one of them.

An alternative representation of path P would be the node sequence

P' = (v ,v , ...,v ) 1 2 n+1
where for each i , arc e starts at node v and ends at node v

i i 1+1

P' is a unique representation of P if and only if each arc e is

uniquely determined by its starting and ending nodes, i.e. if for each

node pair (v,w) there is at most one arc from v to w . In this

paper we are interested only in shortest paths. Therefore we can assume

without loss of generality that at most one arc leads from v to w , since if multiple such arcs exist only a single minimum length arc among

them is needed for shortest paths between any node pair.

A network containing M arcs and N nodes may be represented in

the computer in several ways. One way, which we will call the matrix

representation, considers all possible pairs of nodes (v,w) and stores

for each pair either the length of the arc from v to w , or o° if no such arc exists. This information may be stored in an N by N

matrix. However, for many applications N is quite large and M is

2 small compared to N , so that most of the entries in the matrix are °° . In this case storing the entire matrix in the computer is inefficient,

and if N is large it may well be impossible.

A second way of representing a network, which will be called the

ladder representation, requires listing all the arcs in the network.

For each arc we need to know its starting node, its ending node, and

its length. Therefore the ladder network representation requires 3M

storage locations. However, if the arcs in the network are ordered by

starting node so that all the arcs starting at the same node appear

together, only N + 2M storage locations are needed, since one only

needs to know which is the first arc starting at each node v . One

can then determine the last arc starting from v as the arc immediately

* The programs for the shortest path algorithms described in this paper,

however, do calculate correct path lengths when multiple arcs exist for

the same node pair.
preceding the first arc starting at node v + 1. (This of course

assumes that the nodes are numbered sequentially from 1 to N . If the

nodes do not naturally appear in such a fashion, it will be necessary

to convert them to this form since efficient operation of the algorithms

requires that nodes be numbered sequentially.) The representation of a network in which all the arcs starting at the same node appear together

is called forward star form, and the forward star of node v consists

of all arcs starting at v . Consider for example the network

where the node numbers appear in circles and the arc lengths are presented next to the arcs to which they apply. This network may be represented in ladder form by the following lists.

arc number beginning node ending node arc length

1

2

3

1

2

2

3

2

1

3

3

5

2

3

4

(Note that only the last three coliomns require computer storage

locations .

)
The same network is represented in forward star form by the following

lists.

arc number

ending

node

arc length

1

2

3

4

2

1

3

3

5

2

3

4

node

number

first arc starting

at this node

1

2

3

1

2

4

(Again the columns headed "arc number" and "node number" do not actually

require computer storage locations.) Two of the lists, that labeled

"ending node" and that labeled "arc length", are the same in the two

forms. The third list (labeled "beginning node") required by the ladder

representation is replaced in the forward star form by the list giving

the number of the first arc starting at each node.

Corresponding to the two fundamental ways of storing a network are

two basic methods for treating shortest path problems: matrix methods

which use the matrix representation of the network and labeling methods

which utilize ladder or forward star representations.

Matrix methods yield the shortest distances between all pairs of

nodes simultaneously. Because of their large storage requirements

their application is restricted to relatively small networks. The

computational effort of matrix methods depends only on the number of

nodes and is independent of the actual number of arcs present in the

network. For this reason, matrix methods tend to be less efficient if

only a relatively small percentage of possible arcs in a network are realized. Most large practical networks are, however, of this kind.

It is for this reason, that this paper concentrates on labeling methods.
3. TREES

The purpose of this paper is to categorize labeling algorithms for

determining shortest paths, to identify some of the "strategies" characterizing these algorithms, to formalize their descriptions, and to

document computational experiments aimed at assessing the relative merits

of the various algorithms for different types of networks. This section

will contain some additional definitions required for describing network

structures as used by the labeling algorithms. The basic labeling

algorithms themselves will be given in the next section.

In the context of directed networks, a rooted tree , or simply tree,

is a network T together with a node r (the root ) , such that each node

of T , except r , is accessible from r by a unique arc-simple path

in T . Alternatively the network T is a tree if

1.) every node of T-{r} is the end of exactly one arc in T , 2.) r is not the end of any arc in T , and

3.) there are no circuits in T . We call a rooted tree T a minimum tree (in the larger network

under discussion) if T contains all nodes accessible from r , and if

for each node v in T , the unique path in T from r to v is a shortest path from r to v in the network. The phrase shortest path

tree has the same meaning.

The standard shortest path problem for a network reads:

Problem 1 Find a shortest path from a given node r to a given

node V . A second, related problem reads:

Problem 2 Find a minimum tree rooted at r . Such a tree always

exists, although it may consist of the node r alone.

The labeling algorithms described in this report solve Problem 1 by

actually solving Problem 2, thereby simultaneously determining the

shortest paths from r to all nodes accessible from r . Conditions 1 and 2 of the second definition of "rooted tree" given

above insure that the tree T can be described in a computer by a list

of length n-1, where n is the number of nodes, including r , in the

tree. This list contains, for each node wfr in the tree, the starting

* If all network nodes are accessible from r , then n=N the number

of nodes in the network.

8
node V of the single arc in the tree terminating at w

Consider the following tree.

(Note the sjmibol 1

1 TTi i

'

i indicates that node 1 is the root. This tree

can be described by the following "predecessor list".

node number predecessor

1

2 1

3 1

4 3

5 4

6 3

7 3

In the algorithms which will be described below, another list,

indexed by the node numbers and associated with the tree T , is required.

This list contains for each node v a label d(v) , the length of the

single path from r to v in T . Nodes not in T may or may not be

labeled; usually they are given the label °° . The root r has label 0.

* We have used the zero here to denote the fact that node 1 is the root

of the tree.
4. BASIC LABELING METHODS

Labeling methods for computing shortest paths can be divided Into

two general classes, label-correcting and label-setting methods.

The typical label- correcting method starts with any tree T rooted

at r and "corrects" T until no further improvement or enlargement

is possible. Label-setting methods start out with the tree T consisting of r alone, and augment T one arc at a timfe in such a manner

that at each step T is a minimum tree for all nodes ija T . Termination for a label-setting method occurs when all arcs which start in

T also end in T , or if the goal was to determine the shortest

paths only to a subset S of nodes when all nodes in S are in

the tree.

We now give a more precise description of each of these two methods

In both methods each stage of the algorithm is characterized by a tree

T rooted at the node r . In the descriptions below £(e) is the

length of arc e and d(v) is the label of node v , equal to the

length of the unique path in T from r to v . The basic lab el- correcting method is as follows:

(1) Start with any tree T rooted at r and with labels d(v)

equal to the length of the path in T from r to v whenever

such a path exists; otherwise d(v) : = °°

. If no other tree is

readily available, set T to be the tree consisting of the root

node r alone (and no arcs) , and set

* The notation a: = b will be used to denote the operation of transferring the contents of computer memory location b to the location a

10
(2) Find an arc e from node s to node t , such

d(s) + 1(e) < d(t) .

Then redefine

d(t): = d(s) + £(e) ,

and adjoin e to T , removing any other arc in T

which ends at t .

(3) Repeat (2) until, for all arcs e

d(s) + Jl(e) >^ d(t) .

The tree T will then contain a shortest path from r to all nodes

accessible from r , and for each node v , d(v) will be the length of a shortest path from r to v . The basic label-setting method is as follows:

(1) Set T: = {r} and d(r): = .

(2) Among all arcs e which begin at a node s in T and

end at a node t not in T , find one that minimizes

d(s) + lie). Put that arc into T and define

d(t) : = d(s) + 1(e) .

(3) Repeat (2) until all arcs that start in T also end in T . The tree T and the labels d(v) then contain the shortest paths and

their lengths as above.

It should be noted that label-setting methods work only for nonnegative arc lengths. If there are no circuits of negative length

present, then label correcting methods will still work even if there are some arcs of negative length.

Flowcharts for the computer implementation of these two basic

algorithms appear later in section 9, in addition to variations on these

two basic methods which utilize the list processing techniques described

in the next two sections.

11
5. TECHNIQUES TO IMPROVE THE LABEL-CORRECTING METHOD

In the description of the basic label-correcting method, step (2)

involves finding any arc e which can be added to the tree with a decrease in the label of its terminal node t . The first observation

which can be made to improve this basic algorithm is that one needs to

look for such an arc only among those arcs whose starting node s is

already labeled with a finite number. The implementation of the basic

label-correcting algorithm described in section 9 (as algorithm C) uses

this observation. In fact, none of the algorithm implementations given

in this paper actually examine the whole arc list at each step; all focus

on arcs in the forward star of a node which meets certain criteria which

depend on the algorithm. The order in which forward stars of nodes are examined is a major factor in the efficiency of the algorithm, and the

techniques reported below are mainly aimed at obtaining an efficient

ordering.

One observation which can aid in determining which forward stars

should be examined (and when) during the course of the algorithm, is that one need examine a node only if it has not been examined since its label

was last changed. This can be accomplished through the use of an alteration flag for each node, which is set when the label to that node

is changed and remains set until the entire forward star of that node has

been examined. Algorithm CI , described in section 9 below, implements

this process. In each pass of algorithm CI , the node list is searched

in order and the forward star of each node whose flag is set is examined

for arcs which should be included in the tree. Termination occurs when

no more flags are set.

12
The forward stars of nodes need not be examined in numerical order

as above; they may Instead be examined in the order in which the nodes were labeled. That is if node v was labeled before node v , then

1 2 the forward star of v is examined before that of v , regardless of

1 2 the node numbers v12and v . The technique employed here is the

sequence list . Nodes are placed on the sequence list as their labels

are altered, and removed from the list as their forward stars are

examined. If the forward stars of nodes are examined in the order in

which they are placed on the sequence list, the list is said to be

treated in a FIFO (First-In, First-Out) manner; if the forward star of

the latest node added to the list is examined before that of a node

placed on the list previously, it is said to be treated in a LIFO (LastIn, First-Out) manner. In general examining the list in a FIFO manner

is much better than the LIFO alternative, since nodes in some sense "closest" to the root are examined before those further out in the tree.

No alteration flag is necessary when using a sequence list since one examines the forward stars only of those nodes which appear on the list.

In algorithms utilizing such a list, termination occurs when the list is

empty.

There is one problem which may arise in using a sequence list. If

a node is placed on the list whenever its label is changed, the same node

may appear in more than one position on the list. This means that the

number of list positions required may be more than the number of nodes.

One way to avoid this situation is to use a flag indicating, for each

node, whether or not it is already on the list. A node already on the

list is not added a second time. If nodes appear at most once on the

list, the length of the list may actually be considerably less than the

number of nodes, since positions are required only for the maximum number

* If a path in T is extended from its end node before the labels of

nodes closer to the root have been lowered, the extension will have to

be relabeled later on.

13
of nodes on the list at any one time. The list may be treated in a "rotation" manner through the use of two pointers u and v , where u points to the entry whose forward star is to be examined next and v is

the position of the last node added. As u moves down the list, there

is unused space at the top of the list above u which may be used for

new nodes when space at the bottom of the list is exhausted. Algorithm

C2, described in section 9 below, employs a FIFO sequence list on which

nodes appear at most once and which is treated in this rotating manner.

By the branch B(v) attached to v , we mean the set of all nodes w 71^ V in T for which the unique path in T from r to w contains

V . Another observation which can be used to improve label correcting

methods is that if the label of node v is decreased by an amount A the labels of all nodes in the branch attached to v may be decreased

by A . It is still necessary to reexamine the forward stars of these

nodes since their labels have been changed, but the reexamination is

done using the new lower label. Algorithm C3 utilizes this observation

by employing a forward pointer f which arranges the tree nodes in

order so that nodes on the same branch appear together. Pointer f has

the following properties:

1) f(v) = r for exactly one node v ,

2) for every node in the tree, there is an integer k such that

f (r) = V , and

3) for every branch B (v)

a. for each node seB(v), there is an integer j such that

f (v) = s , and

b. if B(v) ^ $ , then there is a unique node w£B(v)

such that f(w)^B(v) . The dotted lines in the following diagram illustrate such a forward

pointer f .

14
All such forward pointers have the property that if v is on the path

in T from r to w then there is an integer k such that f (v) = w. This follows from property 3a and the definition of a branch.

When the label to a node w is changed, in addition to decreasing

all labels on the branch attached to w , it is necessary to detach the

branch together with w from the old predecessor v of w and to

reattach them to the new predecessor v of w . This necessitates a

2

change in the forward pointer.

Suppose w and the branch B(w) are to be detached from v

1

If w = r , the empty tree will result. If w ^ r , there is a node s such that w = f (s) . One finds s by starting at the old predecessor

V- of w . Since w is in B(v, ), there is some k such that

k k-1

f (v ) = w , and the node s = f (v ) is such that f(s) = w . Let

t be the "last" node in the branch B(w); that is, t is in B(w) but

f(t) is not. (Property 3b insures that t exists.) Then w and the

branch B(w) may be detached from the tree by setting f(s): = f(t),

and removing the pointer f from t .

15
Attaching the branch B(w) together with the node w to the node

V involves setting f(t): = f(v ) and f(v ): = w , as well as updating the predecessor of w to be v . As an example, node 5 and its branch {9,10} in the preceding

diagram are detached from node 2 and reattached to node 3 in the

following two steps:

1. Detach node 5 and its branch {9,10} from node 2.

2. Reattach node 5 and its branch {9,10} to node 3.

nrrm

16
The basic label-correcting method has been ascribed to Moore [41],

and appears both in Ford and Fulkerson [15] and Berge [4]. Bellman [1]

has described a slight variant. The alteration flag technique used in

CI is described by Bock, Kantner, and Haynes [5] and also by Hoffman

and Pavley [23]

17
6. TECHNIQUES TO IMPROVE THE LABEL-SETTING METHOD

Sequencing techniques and lists are also used to Improve the basic

label-setting algorithm. In the process of finding an arc from a node

In the tree to one outside the tree which yields the "minimum tree

extension" (Step 2 of the basic label setting method; see section 4),

many possible labels are calculated and discarded. The Improvements

described below all Involve retaining this information (as temporary

labels) to avoid recalculation. Indeed, the algorithms are designed

so that each arc is examined only once. The first improvement, implemented in algorithm SI, Involves

keeping a sequence list of nodes not yet in the tree linearly ordered by

their temporary labels. Each of the nodes in the sequence list is thus

accessible from at least one node in the current tree by a single arc,

and its position in the list is determined ^-y the label it would have

were that arc to be adjoined to the tree. If there is more than one such label for one node in the list, its position is determined by the

minimum label. Thus if the temporary label for a node v is lowered

because of an addition to the treej v must be moved up in the sequence

list. Adding a node to the list or moving one to a new position involves

searching the list to find the position which that node should occupy.

At each step the top node on the list, i.e. the node which has smallest

temporary label, receives its permanent label (equal to its latest

temporary label) , and its forward star is the next to be examined.

This procedure consumes a great deal of time in finding the position

a node should occupy when it is first added to the list or when its

temporary label is changed. The other algorithms reported here are designed to reduce the time spent in these actions. In the first

modification, implemented in algorithm S2, the list is partially ordered

in a tree sorted form , rather than linearly ordered. The elements of

such a list may be considered nodes in a binary tree (not to be confused

with the minimum tree) . A binary tree containing n nodes is a tree in

which for some k <_ n , each node numbered less than k has exactly

two arcs starting at it, node k has either one arc or no arcs starting

at it, and nodes k+1 through n have no arcs starting at them. The

elements of a tree sorted list can be considered nodes of a binary tree

18
in which the label of the predecessor of any node never exceeds the label

of the node. The tree nodes can be sequentially written in successive

horizontal layers, the first being of cardinality 1, the next of

j_"L cardinality 2, the next of cardinality 4, and the k of cardinality

k-1

2 . The labels of nodes in any path in the binary tree are linearly

ordered, but nodes on different paths are non-commensurable.

Suppose for example that one has the following nodes and labels in

the shortest path tree, and wishes to keep the nodes in a list treesorted on label:

node

1

2

3

4

5

6

78

9

10

label

5

4

4

2

9

10

12

3

1

2

One may construct the following binary tree having the property that the

label of the predecessor of any node in the binary tree never exceeds the

label of a successor in the tree.

19
This binary tree is stored in list form in the computer as follows on

the left.

tree list labels

9 1

10 2

3 4

4 2

8 3

1 5

7 12

2 4

6 10

5 9

Although the list is in tree sorted form, a glance at the associated

list of labels on the right shows that it is clearly not in linear

sorted form.

Tree ordering guarantees that the top element in the list has

minimum label, but tree ordering requires much less work to establish

and update then linear ordering. In fact, if there are n elements in

the list, the tree sorting procedure only requires at most k comparik+1

sons, where k is the first integer such that 2 > n , to find the

position to be occupied by a new list entry. To accomplish this, the new entry is tentatively put in the (n+1) st position. It is then

compared with the entry in the position (n+1)/ 2 (which is in the next

higher horizontal layer) , and is interchanged with that entry if it is

less. This interchange process is continued until the new entry is

greater than or equal to some old entry and no interchange takes place,

or else the new entry becomes the top entry in the list. Although

adding a node to the tree-sorted list requires less work than adding to

a linearly sorted list, the tree-sorted list requires additional reordering when the top element is removed. This procedure, too, takes no more

than k steps where k is as above.

20
The implementations of the algorithms described in section 9,

require that arc lengths be non-negative integers. Label-correcting

algorithms will work correctly if arc lengths are negative, so long as no negative-length circuits exist, but label-setting algorithms will not

work correctly on such networks. The integrality requirement is necessary only for algorithm S4, but in practice this requirement is not

unduly restrictive for the other algorithms as well. In most practical

applications using shortest path algorithms, the arc lengths are either

integers or can be transformed to integral values by using an appropriate

scale factor.

Once this transformation has taken place, if the maximum arc length

is small (say compared to the number of nodes) , advantage can be taken of

the fact that many of the temporary labels are the same. This equality

of labels arises from the further observation that the difference between

the largest and smallest temporary labels is at most the length of the

longest arc (this is true because, for label-setting algorithms, the

smallest temporary label is at least as large as any permanent label, and

a temporary label is the sum of a permanent label and one arc length)

Therefore if the number of temporary labels on the list is large compared

with the maximum arc length, one would expect many such labels to be

equal.

Algorithm S3 of section 9 takes advantage of this fact by "chaining ties" in such a manner that when the sequence list is searched for

the position to be occupied by a new entry, the label of only one of the

nodes in a chained group need be examined since all others have the same

label. The chaining process is accomplished by having a pointer (b in

the example below) to the first element of the first chain and the first

element of each succeeding chain and another pointer (s in the example

below) to successors of elements within a chain. These are illustrated

in the following example.

21
7 ^ ^ 3 i ^ » 9

The numbers in the boxes represent node numbers. To find the

position to be occupied by a new node, one need only check through the

sequence of nodes given by the pointer b . In the example, this means

checking at most four entries rather than possibly ten.

Algorithm S4 of section 9 takes more direct advantage of the

observations above. Instead of using a sequence list in which the

position of a new entry is determined by a search or sorting procedure,

this algorithm puts a node in a list position determined directly by the

temporary label of the node, modulo the maximum arc length plus 1. Since

several nodes may have the same temporary label, this list also uses

the chaining procedure described above. In addition it is treated in a rotating fashion, using a single pointer to the position of the current

top node, to eliminate having to move chains up the list whenever the

current maximum permanent label is changed.

The basic label-setting algorithm is credited to Minty by Pollack

and Wiebenson [39], and is also described by Hu [26]. A slight variant

is described by Dijkstra [11] and by Whiting and Hillier [61]. The treesorting technique used in algorithm S2 appears in Knuth [30]. Algorithm

S4 is credited to Loubal by Hitchner [21] and also appears credited to

Dial [10].

22
7. EXPERIMENTAL RESULTS

The seven algorithms CI, C2, C3, SI, S2, S3, and S4 were programmed

from the flowcharts given in section 9 In FORTRAN V (UNIVAC's expanded

FORTRAN IV), and were run under the EXEC II operating system on the

UNIVAC 1108 at the National Bureau of Standards. This computer has an effective cycle time of 375 nanoseconds and 65,536 36-bit words of core storage of which about 53,000 words are available to the user. Copies

of the programs appear as an appendix. The FORTRAN language was chosen

because its wide availability makes it probable that in many applications of shortest path algorithms, this computer language would be used.

No attempt has been made to take full advantage of peculiarities of the

UNIVAC FORTRAN V compiler in order to obtain the fastest version of any

program. However, it is hoped that because all programming was done by

one person and the algorithms all used the same network structure, none

of the algorithms was given a special advantage over the others resulting from any programming quirks.

In the experiments described below, all seven algorithms were run

to compute the same trees in the same networks. The UNIVAC 1108 internal

clock was interrogated before and after computation of each tree to

obtain the actual computation time for that tree. No input or output

time is included in these timings, but time for the algorithm initialization steps is included since it is part of the time required for

computation of each tree.

Original timings (not reported here) of the shortest path algorithms

were performed on highway networks prepared for use by the U.S. Department of Transportation's Northeast Corrider Transportation Project. It soon became clear that these medium-sized networks were too small to

provide meaningful time distinctions on the UNIVAC 1108 computer. In

addition, these networks all had arc/node ratios (the aver^age number of arcs starting at a node) of between 3 and 4, which is typical of highway networks, whereas it was our purpose to compare the performance of

the algorithms on a wider range of types of networks. For these reasons

it was necessary to devise programs to generate a variety of quite large

network types. Three computer programs were written and have been used

23
to produce the networks upon which the comparative timing runs were made.

All three programs create directed networks with the nodes numbered se- quential from one to the number of nodes, and with (Integer) arc lengths

randomly assigned between zero and a desired maximum arc length (MAX H In Table 1)

.

The first program creates a p by q rectangular grid network

whose nodes are numbered sequentially from left to right and then top to

bottom. The number N of nodes Is thus pq and the number M of arcs Is 4pq - 2p - 2q . Since arc lengths are randomly assigned, the

length of arc (a,b) Is unlikely to equal the length of arc (b,a). Thus,

although the networks created by this program have the connectivity of a grid, the triangle property may not hold and distances are not S3mfflietric.

A second program creates a complete network on N nodes, that Is,

a network containing an arc from each node to each other node, N * (N-1) arcs In all.

The final network-generating program creates random connected networks with a specified number of nodes N and arcs M . The program

first creates a spanning tree rooted at node 1 (i.e. a tree in which all

other nodes in the network are accessible from node 1) . This is done by

starting with a tree containing only the root, and augmenting it at

every stage by an arc (a,b) , where a is a node chosen at random from

those nodes already in the tree and b is chosen at random from those

nodes not in the tree. The final M - N + 1 arcs are then obtained by

randomly choosing pairs of nodes from the set of all possible node

pairs. Starting with a spanning tree rooted at node 1 Insures that all

nodes are accessible from that node at least. In practice this has been

true as well from other nodes chosen as root, and timings are included

only for trees for which this was so.

* Although the discussion in section 2 excluded networks containing

multiple arcs for the same node pair, the computer programs given in the

appendix to this paper actually calculate correct shortest path lengths

for such networks. The generation procedure for random connected networks therefore allows multiple arcs, since additional effort is required

to exclude them.

24
Table 1 gives timings for the seven algorithms as applied to 13

different networks created by the three programs described above.

(Storage considerations are discussed later.) Each timing number reported in the table is the average of the times for five separate trees

(corresponding to five roots) in that network. For all the grid networks the five root nodes chosen were 3, 366, 729, 1092, and 1455 to

insure that the trees were computed from five quite different network

positions. For all the complete and random networks trees were computed

from the nodes numbered 1 through 5. It should be remembered that the

absolute magnitude of the time to compute a tree will vary from computer

to computer; still the relative times should be rather similar for

different machines.

The 13 networks used in the tests reported in Table 1 are believed

representative of the types of large networks found most often in the

shortest-path applications for which labeling algorithms are most suitable. Those networks with arc/node ratios between 3 and 4 are typical of

large ground transportation (auto or rail) networks, while those with

ratios between 5 and 20 are representative of many communications and

air transportation networks. Networks containing fewer than one or two

hundred nodes can be handled using matrix algorithms, since the whole

matrix of distances can be stored at one time in the computer. Realworld applications in which there are more than a few hundred nodes and

the matrix of arc lengths is not sparse are seldom found primarily (one

supposes) because of the difficulties in gathering, checking, and processing so many data. For instance, the complete network on 500 nodes

would contain about 250,000 arcs. If even 10 percent had to be included

as separate pieces of input data, 25,000 data points would have to be

coded and checked for accuracy.

* Additional computational experiments, not reported here, support the

representativeness of the times in Table 1. Also the variation among

the times for the computation of each of the five trees by the same algorithm is generally less than the differences between algorithms.

** In addition, economy considerations work against designing realworld networks with much multiple connectivity.

25
C/3

00in CO

CO o

-vl- in CM -*

•<jen CO f^ r^ CM CO O o ON in 00 CM CM r^ 00

en i^ CO CM ON r- ON 00 ON 00 <f <r in CTv tH iH T-i o O o T-\ CM CO o o O 00

H i-i in

rH <3^ CO r^ r^ 00 CO r^ CJN CM r-. CO CO

Pi <N <d- CM CM o 00 in CTv in r-{ CO CO i^ CM o en » • • • • • • • • • • • • fn rH iH iH rH o o o rH CM o o o CM QW^^

iH VO in •vl- r-- vO r-. in CvJ 00 CJN o CM CM

en v£) r^ <r (Ti ^D <f CO rH 00 <r

m <r

O

w • • • • • • • • • > CN rH iH O o CO CJN CJN v£) o o o ON < rH CM CM

w

w CO 1^ CO o CO r^ <JN VO CM CTN r^ o -dH w CO O CO cy\ in rH r^ 00 CJN O <r -d- in O S Pi U • • • • • • H CM Csl CM -d- OC) o o O rH o o 1^ <-\ M w

pcj o W w r^ in in ON in o r^ o <r r^ CO vD CM ^ w CM rH a\ o> ^ CM ^ vD 1^ r^ <f vt CO r-~ ^*^ o • • • • * • • • • • • • • W w

rH rH CM <r 00 o O o o o o o o o o

12: s M M CO CO r--. v£) >* CM C7N CO o o 1^ CO Cv| s S rH CO CM in Csl CM vO ^ r^ 00 <r CO CO 00 M 1—1 U • • • • • • • • • • • • • H H rH CM <r in CJ^ o O o o o o CO o

T-\ > K W H o^

hJ

H

pq <ri ^ o O o o O o o o o o o rH o

<; c2 ^ o O o o O o o o o o o o H o

T-i rH rH rH rH rH rH rH ,-\ tH rH oCO

u en o O o o O o o O o o O o o u o m r-\ 00 <3N o O O o o O CJN o

p^ Pi 00 r^ r^ <r <3N o O

O o CJN On C3N o o <^ 0^ CJ^ a\ CTi 00 o

r-{

OOrH o

rH

<7n CJN 00 o

rH

CO

EH en hJ w o o o o O o O o o o O

O o • P Q o o o o O o o O o o O O o ji: w O in in in in in in o O o rH i-{ in o 4J M S CM CM CM CM CM <-i CM CO CM CO 00

Pi S 3oM o in o o o

rHou

O

H o o CM in o o CO

g

M

inX

rHX

rHXCMXinX

inX

B

W Pi o in o o in

m 3 ^ u

enWQ

in CM Csl rH

•HX

CO I

Pi

QM

Pi

QM

PioPi

Hw

h4O

HHO Pio

CM in ^ 00 CM

26
Algorithm S4 is clearly the fastest often by a wide margin

in most of the cases reported in Table 1. In addition, its time is most

consistent, depending primarily on the number of nodes rather than on network configuration. The speed of algorithm S4 is undoubtedly due to

being able to enter nodes directly on the distance list with no sorting

at all. However, accuracy requirements or storage limitations may make

it impossible to set up this distance list, and may thus make other

candidates more suitable in some applications.

The label-correcting method depends, in some sense, on the number

of arcs in the shortest path having the greatest number of arcs, since

in general at the k pass one is attempting to extend paths with k-1

arcs. Therefore label-correcting algorithms require much longer time

for computing trees in "long thin" networks, such as the 5 by 500 grid

(network 5 in Table 1) in which the shortest path from one of the corner nodes to that diagonally opposite it contains at least 505 arcs, than

for a more "round" or "square" network, such as the 50 by 50 grid network (network 1 in Table 1) in which a similar shortest path would

contain only about 100 arcs. The label setting algorithms, on the other hand, depend primarily

on the number of nodes in the network, since at each pass a new node is

added to the tree. Of course the extra sorting required by some of the

algorithms greatly increases the number of steps in a single pass. This seems particularly true for random connected networks in which the arc/

node ratio is small. In such networks there are not many alternate paths

to the same node, so that much of the sorting required by the labelsetting algorithms does not contribute to a decrease in the number of

steps' required to find a shortest path tree. As an example, if the

original network were actually a tree rooted at r , then the order in

which forward stars are examined does not matter so long as those for

nodes in the tree are examined before those for nodes not yet in the

tree. In this case all sorting is unnecessary.

A shortest path in network 12 is essentially one which has fewest

possible arcs in it, since all arc lengths are exactly 1. (Zero length

arcs were allowed in the other networks, but not in this one.) Algorithm

27
C2 performed particularly well on this network, since in this case each

node appears on the sequence list exactly once, and the list is ordered

in such a manner that nodes at the top of the list are one arc from r , nodes directly below are 2 arcs from r , etc. In algorithm CI nodes

are examined in numerical order, rather than in the order in which they

were labeled, necessitating more than one pass through the list.

Algorithm C3 requires much time in setting up the lists for detaching

and reattaching branches, a situation which never need occur for this

network. In addition, sequencing by the inverse of the forward pointer

means that in some cases nodes further out on a branch are examined

before nodes closer to the root, an undesirable condition for this network.

Network 13 has the same connectivity properties as network 9 (i.e.,

if arc (a,b) exists in network 9, arc (a,b) also exists in network 13 and

conversely), but it has different, and in general longer, arc lengths.

As can be seen from Table 1, algorithm S4 begins to lose its advantage

over label-correcting methods when the distance list, whose length is

determined by the length of the longest arc, has as many entries as the

number of nodes. The algorithms SI, S2, and S3 which require sorting a list of this length are much less efficient. Chaining ties (in algorithm

S3) does not greatly improve the linear sort, since there are fewer ties

than in networks with shorter arc lengths.

The timings reported for network 13 illustrate a point which the

authors believe is often missed by those comparing algorithms: the

precise list processing techniques can greatly affect the efficiency of

the basic algorithm. Therefore we wish to stress that it is not sufficient to describe an algorithm in general terms or give a reference to

such a description, when several different list processing techniques

are available and the general description is not specific enough to

indicate which was actually used. As a dramatic example of this, an algorithm similar to C2, except that the sequence list was treated in a LIFO (rather than FIFO) manner, was run on network 1 and required more

than one minute for a single tree, as compared with the slightly more

than one second required by C2 to compute the same tree.

28
Label-setting algorithms cannot be used to compute trees in networks

containing negative arc lengths, since they are based on the assumption

that nodes can be added to the tree in the order in which they are labeled. If the shortest path from node r to node a goes through node b,

the label for the path to b must then be less than the label for the

path to a' . This may not be the case if negative arcs exist. The

following network illustrates this point.

The label-setting algorithms start by examining the forward star of the

root node 1, reaching both nodes 2 and 3 from node 1. Since all arcs beginning in the tree also end in the tree, the algorithms terminate at

this stage. The path 1 to 2 to 3 is never examined for possible inclusion in the tree. Label-correcting algorithms, on the other hand, will

examine this path, since they terminate only when no further path

improvements are possible.

The number of computer storage locations required varies for each

of the seven algorithms. If N is the number of nodes and M the

number of arcs in the network, all algorithms require 3N locations for

the arrays a, p, and d, and 2M locations for the arrays n and Z . (These arrays will be described in the next section.) The seven algorithms all require additional storage which is summarized in Table 2,

where "node arrays" are arrays requiring one full location for each node.

"Boolean node arrays" require one bit for each node, and "max arc length

arrays" require a number of full storage locations equal to the maximum

arc length. Thus algorithm CI requires the least amount of storage and

is also comparatively fast except on the long narrow networks which

none of the label-correcting algorithms performed well on. C2 requires

only one additional list and is consistently better than CI. It is

particularly recommended for networks in which the arcs are all

29
TABLE 2

ADDITIONAL COMPUTER STORAGE REQUIREMENTS FOR

SHORTEST PATH ALGORITHMS

ALGORITHM

CI

C2

C3

SI

82

S3

S4

NODE ARRAYS

BOOLEAN

NODE ARRAYS MAX ARC LENGTH ARRAYS

30
approximately the same length, so that the shortest path between two

nodes is very likely to be the path having fewest arcs.

In conclusion, algorithm S4 is recommended whenever it is feasible

to set up the distance list which it requires. For networks whose arc lengths do not permit setting up such a list, one of the two labelcorrecting methods CI or C2 is recommended, depending on the amount of

computer storage available.

31
8. FLOWCHART CONVENTIONS

This section will describe several conventions adopted for the flowcharts in section 9 • The operations used in shortest path labeling

algorithms consist, for the most part, of putting information into or extracting information from various lists. The information to be hkndled takes three possible forms:

1) integer numbers,

2) the Boolean values, "YES" and "NO", and

3) positions in lists (usually node numbers

or arc numbers)

.

Convention 1 : Names of storage locations containing integers or Booleans

consist of three capital letters, e.g. TES, AUX, CAN. Single lower case letters will be used to denote storage locations containing list positions, e.g. v,w,e.

Convention 2 : List functions whose values are integers or list positions

will be denoted by single lower case letters, e.g. d(v), p (w) , a(u).

List functions whose values are Booleans will be denoted by single

capital letters, e.g. C(w), T(u), H(v)

.

Convention 3 : Rectangular boxes will be used for operations which

transfer information from one location to another and also for arithmetic operations. (The only arithmetic operations involved in the

shortest path algorithms are addition, subtraction, multiplication, and

division. These last two are required only in algorithm S2.) Examples

of such operations are:

d(v):=CAN

t

This puts the value of CAN into position

V of the list function d . i

e:=a(u)

T

This extracts the value in list position

u of list function a and puts it into

location e .

32
1

CAN:=TES

!

1

MEM:=YES

4- 1

TES:=CAN+AUX

t

This shifts the value In TES into

location CAN.

This makes the Boolean variable MEM

have value YES

This puts the sum of the variables

CAN and AUX into the location TES.

Convention 4 : Diamond-shaped boxes will be used for conditional transfer operations. Examples of these operations are:

Transfer on equality. If v=x continue

in the YES direction, otherwise in the

NO direction.

Transfer on comparison. If the value

in CAN is greater than that in TES

continue in the YES direction, otherwise

in the NO direction.

Boolean transfer. If the Boolean variable

MEM has value YES continue in that direction,

if NO in the NO direction.

33
Convention 5 : The list operations of initiating, continuing, or retracting a list pointer will be denoted by the following types of boxes.

i

INITIATE

NODE LIST

V

''

CONTINUE

STAR LIST

1

END

This loads v with node number 1, the

first position in the node list.

This loads e with the position following

the one previously contained in e . The

END exit is used when the previous position

was the last in the list.

RETRACT \

NODE LIST^

END

This loads v with the position before the one previously contained in v . The END

exit is used when the previous position of

V was node 1, the top position in the list,

Convention 6 : Circular disks will be used to denote locations in the

code. In particular:

denotes the beginning, and

denotes the end of each algorithm.

Convention 7 : The following lists and variables will be used in all

algorithms

.

34
a(v) denotes the mapping from the node list to the

top entry of the star list for each node. The

value of a is usually an arc, but it may also

be the symbol EMPTY if there is no star list

for node v .

n(e) denotes the mapping from the arc list to

the node list giving the terminal node of arc e .

£(e) denotes the length of arc e .

d(v) denotes the label for node v .

p(v) denotes the node which is the predecessor

to node v in the shortest path tree.

contains the position of the root in the

node list.

35

9 . ALGORITHMS

This section contains descriptions and flowcharts of the basic

label-correcting and label-setting methods, and the variations of these

basic algorithms discussed in sections 5 and 6. FORTRAN computer

programs implementing each of these algorithms appear as an appendix.

37
C: basic label-correcting . This algorithm realizes the basic labelcorrecting method given in section 4. The algorithm starts with the

root having label zero and all other nodes having infinite label. The

node list is searched in order (boxes 1 and 14) at each stage. Forward

stars of all nodes with finite labels are examined (boxes 3 through 6,

and 13) for arcs e which can be adjoined to the tree to diminish a label (boxes 7 through 9) . Once such an arc is found the label and tree are updated (boxes 10 and 11) . The Boolean variable MEM is used to

indicate whether, during the search through the node list, any labels

have been changed (box 12) . Termination thus occurs when MEM remains NO

throughout a complete search of the node list (box 15)

.

38
C: BASIC LABEL CORRECTING

(I)

(2)

(3)

(4)

(5)

(6)

(7)

(15)

YES ^^^\ NO

A J < <r MEM > > s

INITIATE

NODE LIST

V

mem: = NO

END

/CONTINUE

< NODE LIST

AUX: = d(v)

YES

(14)

<b

YES

END (13)

CONTINUE

STAR LIST

w5 = n(e)

INITIATION

d(r)=0

d(v/)=co,if V ¥'r

€> mem: =yES

p(w)J = V

(8) TES5=jl(e) + AUX d(v#): = TES

(12)

(II)

(10)

39
CI: alteration flag . This algorithm utilizes an alteration flag T as described in section 5. The flag T(v) has initial value NO for all

nodes except the root r . It is set to YES only when the label of v

is changed (box 12) and remains YES until the forward star of v is

examined (box 15) . The rest of the algorithm is the same as algorithm

C , except that it is not necessary to test whether AUX is infinite since

T(v) is YES only for nodes with finite labels.

40
Cl: ALTERATION FLAG

(I)

(2)

(3)

(4)

(5)

^VES y i AUX: = d(v)

i

T(v): = NO

el = a (v)

(15)

INITIATION

d(r)=0

d(v) = OO, if v^ r T(r) «YES

T(v) =NO,if v=?t-r

(13)

mem: = YES <

KsMd(w): = TES

(10)

(12)

T(w):=YES

p(w): = V

(ID

41
C2: FIFO sequence list, single entry . This algorithm uses a sequence

list b which Is treated In a FIFO manner. Nodes are added to the

bottom of the list (box 14), Indicated by the pointer z as their labels

are changed, and nodes are removed from the current top of the list

(box 19) , Indicated by the pointer v . The list Is treated In a rotating manner so that whenever either v or z reaches the end of

the list, It continues at the beginning (boxes 15 and 16, and 21 and 22).

Termination occurs when v = z (box 18), Indicating the list Is empty.

The flag T Is used to Insure that no node appears more than once on the

list (box 12). T(w) Is Initially set at NO and Is changed to YES when

w Is added to the list (box 13) . Once the forward star of a node u has been examined, T(u) Is reset back to NO (box 20).

42
(I)

(2)

(3)

(5)

(6)

(7)

(8)

(9)

(10)

(II)

C2: FIFO SEQUENCE LIST, SINGLE ENTRY

INITIATE

f

NODE LIST

V

z! = V

u: = r

INITIATE

NODE LIST

y

tEND

CONTINUE

NODE LIST

(22)

(21)

e: = a(u)

e^\ YES

(18)

(4) I AUX; = d(uT| (19) I u; = b(v)^|—

1 T(u); = NO | (20)

NO

YES.K^ INITIATION

cl(r) = d(v) =00, if V ?^ r T(v) = NO, for oil V

CONTINUE

STAR LIST

w: = n(e)

TES:=i(e)+AUX

(17)

-> O

INITIATE

NODE LIST

z

If. END

(16)

^YES

d(w): = TES

i

p(w): = u

«w

CONTINUE

NODE LIST ^

YES

b(z): =w

T(w)

(12)

NO

T(w): = YES

(15)

(14)

(13)

43
C3: forward pointer, sequencing by inverse of the forward pointer . This algorithm utilizes a forward pointer f as described in section 5

to implement the process of severing and reattaching branches. The

algorithm also uses an alteration flag H. Sequencing of nodes occurs through the use of the inverse g of the forward pointer (box 19) ; g

being such that if f(u) = v then g(v) = u . SEVER . This section of algorithm C3 decreases the labels on the branch

attached to w by the amount DEL (box 107) , at the same time setting

the flags on all the nodes in this branch (box 108) . Boxes 101 through

106 and 109 find the nodes in the branch attached to w . These nodes

x are indicated by B(x) = YES. This is accomplished by setting

B(w) = YES and following the forward pointer from w until either, for some node v the predecessor of v is not in the branch attached to w , or some node v in the branch has f(v) = r . Boxes 110 through

112 sever the branch from the old predecessor of w , updating both the

forward pointer f and its inverse g ; boxes 113 through 116 reset B

ATTACH. This section of algorithm C3 attaches the branch just severed

to the node v , the new predecessor of w . Again this involves updating both the f and the g pointers. After SEVER, x is the last

node in the branch attached to w . If there is no branch attached to w , then X is w (box 10 of C3) . Otherwise the branch is attached to

V by inserting it in the forward pointer list between v and the old

f(v). Thus f(v) is set equal to w and f(x) is made the old f(v).

44
C3: FORWARD POINTER, SEQUENCING BY INVERSE OF THE

FORWARD POINTER

(I)

(2)

(3)

(4)

(5)

(6)

AUX: = d{v)

e: = a{v)

(7)

(8)

(9)

YES

w! = n(e)

TES:=i(e)+AUX

(21)

YES ^-"^^ NO

MEM > > e

YES

NO

V = r v: = g(v) (19)

(20)

INITIATION

d{r) = 0, d(v) =00 if V # r H(r)=YES, H(v)= NO if V ?*r

fir) = r , g(r) = r B(v) = NO, for oil V

<? —H(v): = NO

J^

(18)

f END

CONTINUE

STAR LIST (17)

(II) >DEL:=d(w)-TES

(10)

(o) SEVER

H(w): = YES

x: « w

d(w): « TES

t

(b) ATTACH

p(w): =

(16)

(15)

(14)

(13)

45

SEVER ATTACH

1109)

(108)

x: = t

H(t): = YES

(107) d(t): =d(i)-OEL -^

s: 9• f (v) (201)

i

fix): = s (202)

i

g(s): = X (203)

J, f (v); ' w (204)

J, g(w): =

(205)

6

47
S: basic label-setting . This algorithm realizes the basic labelsetting method described in section 4. The algorithm starts with the

root labeled zero and all other nodes having infinite labels. During

each pass all nodes are examined (boxes 2 and 15) . All arcs leading

from a node with finite label to a node with Infinite label (i.e. from

a node in the tree to a node not yet in the tree) are examined as possible extensions (boxes 3 through 9) . The current minimum potential

label is stored in CAN, the starting node of the new tree arc in s , and its end in t (boxes 10 through 13) . CAN is initialized at «>

at the start of each pass (box 1) . The algorithm terminates when no new

arcs can be added to the tree, i.e. when CAN is still infinite after all

nodes have been examined (box 16) . If CAN is finite then the node t is added to the tree and its label is made CAN (boxes 17 and 18)

.

48
S: BASIC LABEL SETTING

YES

(6)

w: « n (e)

(9)

(10)

(II)

:CAN<TE

NO

(18)

p(t): = s

(12)

(17)

d(t): = CAN

N0(16)

END

CONTINUE

NODE LIST (15)

INITIATION

©d(r) = d(v) = QO, if VT^r

<

>^ END

CONTINUE

STAR LIST

e (14)

<b

(9

l^ES J k CAN: =TES s: = V V _ .. 1 Ti " ^ 1 (13)

49
SI: sequencing by label, linear sort . In this algorithm, the first time

a node not yet in the tree is encountered (box 12), it is put on the list

b which is linearly ordered by the temporary labels (boxes 13 through

a). The mapping t is the inverse of b, i.e. if w occupies the kth

position in list b , then b (k) = w and t (w) = k . Mapping t is

required in order to find the position occupied by a node w already on

the list when its label is changed, since w will be moved up in the

list from this position by SORT. Two pointers to the list b are used:

s , which points to the current top position, and z , which is the

current last node in the list. There is no need to make a distinction

between temporary and permanent labels, since each node between positions

s and z on the sequence list has a temporary label, while those above

position s and that in s itself are permanently labeled. Boxes 13,

21, and 103 have no END exit since the end of the list will never be

reached

.

SORT . This section of algorithm SI puts w in the correct position in

the list b to insure that the list remains linearly sorted by label.

The instructions in boxes 14 and 15 put w at the bottom of list b

if it is not already on the list (box 12) . Variable y starts as the

position occupied by w and is then retracted (boxes 101 through 103)

.

If the node v in position y has a larger label than w , v is

moved one position down the list. When finally the label of w is

greater than or equal to the label of some node v , w is placed in the

position below v .

50
si: sequencing by label, linear sort

(I)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

a

initiate

node list

b(z): =r

s : = z

t(r): =2

u: = b(s)

> f

c'. * a(u)

YES

Aux: = d(u)

(9) w« = n(e)

> t (10) TES:=i(e)+AUX

i

(M) TEm: = d(w)

initiation

d(r) = d{v) = CD, if V ^ r

CONTINUE

NODE LIST (21)

(20)

END (19)

CONTINUE

STAR LIST

<£> ->-

(13)

CONTINUE

NODE LIST

<d)

(q)

SORT

(?

p(w): = u (18)

d(w):=TES (17)

(17)

51
SORT

(101) y: = t (w)

(102)

x: = y

(103)

RETRACT

NODE" LI ST >->- e

v: = b(y) (104)

t(v); =x

(107)

b(x): = V

(106)

-(l)^5^<d(v)>TES> (105)

^NO

b(x);= w (108)

t(w): = x (109)

52
S2: sequencing by label, tree sort . In this algorithm the sequence

list b is maintained in the tree sorted fashion described in section 6:

if i = [j/2] (fixed point division) then d(b(i)) £d(b(j)). Mapping z points to the next entry to be filled at the bottom of the list. Node

u , the one whose forward star is examined next, starts out as the root

r and from then on is the top node in b (box 19) . The algorithm

proceeds much as in algorithm SI. The procedure SIFT UP puts w in the

correct position in b , and the procedure SIFT DOWN rearranges b to

maintain the tree ordering after the top node is removed. The algorithm

terminates when the list b is empty.

SIFT UP . This section puts w in a position in list b so that the

tree ordering is maintained. Location s contains the trial position

for w . If w is not in the list b , then s starts at the end of

the list (boxes 9 and 10). If w is already in the list, then s starts at the current position occupied by w (box 13) . Variable h is

the position of the "predecessor" of s in the tree sort (box 101)

If there is no such predecessor (box 102) then w is put at the top of

the list. Otherwise the label of w is compared with the label of the

node V in position h (boxes 103 through 105) , and if the label for w is less, V is moved down to position s (boxes 106 and 107). This

process continues until for some value of h , d(v) _< d(w) . Then w is

put in position s . SIFT DOWN . This section reorders the list b after the top node is

removed. The last node q is removed from the list b (boxes 17 and

18) . Since the top node has also been removed (box 19) , there is a free position in the list in which to put q . The SIFT DOWN procedure

searches for the correct such position s , moving nodes up the list

until it is found. Variable s starts at the top position, which is

now empty (box 201). At each stage, h is one of the two positions

2s or 2s+l for which s is the "predecessor" (boxes 203, 207, and

214) . The label of w is compared with the lesser of the labels of

the nodes v in position h and y in position h+1 (boxes 203

through 215). If d(w) is greater than the minimum of the two, the

node having that minimum label is moved up the list, and the new trial

53
position s becomes the position previously occupied by the node which

was moved (boxes 216 through 218) . This procedure insures that the new

top node has minimum label and that the rest of the list remains tree

sorted.

54
(I)

(2)

(3)

(4)

(6)

(7)

(8)

(9)

(10)

S2: SEQUENCING BY LABEL, TREE SORT

INITIATE

£

NODE LIST

u*. = r (H)

e! = a(u)

^YES

.EMPTY> >- e

(5) AUX: = d(u) END

Tend

SIFT

down

RETRACT. ^^

NODE LIST)—^^l)-

(17)

(16)

CONTINUE

STAR LIST <a)

w: - n(e) ^

TES:=-t(e)+AUX

>

r TEm: = d(w)

(13)

s: = t(w)

V^YES 1 \

s: = 2

CONTINUE^

> NODE LIST

Z /

^

(II)

initiation; d(r) = d(v) = 00, if V ^r

-9

u*. = b(l) (19)

q: = b(z) (18)

SIFT UP (a)

p(w): = u 1

d(w): = TES

(15)

(14)

55
(108) s: = h

SIFT UP

(107) t(v): = s

(106) b(s): =v

h: = s/2 (101)

(102)

v: = b(h)

I

TEM:=d(v)

(103)

(104) y

<^^^ <TEM>TIS> (105)

b(s): - w (109)

t(w): 'S (110)

56
9

(200 s:=. 1 i

(202) TES; = d(q)

(203) h : = s X 2

(204)

^YES

(205) v: = b(h)

\'

(206) TEM: =d(v)

i

(207) k: = h + i

(206)

(209)

SIFT DOWN

(218) (217)

s; = h

^[<r-\ t(v)I -

(216)

b($): = V

^NO

k<z > >- YES

y: = b(k)

(210) TEN:=d(y)

(211) <JEII<TEM>—>- (b>

,YES

/k 212) TEM:=TEN

\ f (213) v: = y

N f (214) h' -•- n I - I\

<m) t(q): = s (219)

b(s): =q (220)

©

NO

[ES>TBJ.

(215)

YES

57
S3: sequencing by label, linear sort with chained ties . In this

algorithm the sequence list is maintained in a linear sorted form as in

SI, but pointers are used to chain ties (nodes having the same label) in

such a manner that searching the list for the correct position for a new node involves only comparing the label of the new node with the

label of one of the nodes in any chain. The main part of the algorithm

is similar to SI and S2. Node v is the one whose forward star is

currently being examined. If a node w is to be added to the list

(box b) , then if it is already on the list (box 10), it must first be

removed from its current position (box a) . Two pointers to the list are

used, namely f which points to the next entry whose forward star

should be examined, and z which points to the first entry in the

bottom chain on the list. Box 19 removes the top element in the list

and stores it in v , and f is then advanced to be the new top element

in the list (box c) . The algorithm terminates when there is no top

element (i.e. f=0) after a pass (box 18).

The list is arranged in the following manner, where elements at the

top of the list have lower labels than elements below and elements on

the same line have the same label.

-^

s —

1

f

1^ ^^

u

u

1

(

t

s

^

s ^r r ^ —

>

u

1

1 V

t

s

t

z » ^

—

f is the last element in the top chain and z is the first element in

the bottom chain. Mapping u is only defined for elements which are

the first of a chain, and it points to the first element of the next

lower chain. Therefore u(z) = . Pointer s indicates the next

58
element in the same chain; s is zero for the last element in any

chain. If node v is the first element in a chain, then t(v) points

to the first element in the chain immediately above v , and t(v) =

if and only if v is the first element in the top chain. For elements

within a chain, t points to the preceding chain element. The Boolean

flag H is used to indicate which nodes are first elements ("heads")

of some chain.

REMOVE w . This section of the algorithm is entered whenever a new

lower label is found for a node w which is already on the list. Node

w must be removed from the position it formerly occupied before it can be put in a new position. If w is not the first element of a chain,

then it is necessary only to update the s and t pointers (boxes 103

and 120 through 122) . If w is the first and only element of a chain,

then removing w consists of updating only the t and u pointers

(boxes 105 and 115 through 119) . If w is the first element of a chain

which contains other elements then s(w) becomes the new head of the chain

and the t and u pointers are updated accordingly.

When this section is exited, several conditions hold:

1) the t, s, and u pointers have been updated in such a manner that w is no longer in the list,

2) H(w) = YES, since ENTER w will put w at the head

of some chain,

3) q contains the first element of the chain immediately

above that formerly occupied by w , and

4) y contains the first element of the chain below the

chain containing q . These last three properties are assured in boxes 114, and 123 through

126 , whenever not done in boxes 102 or 104.

ENTER w . This section of the algorithm finds the correct chain for w

and puts w at the head of that chain. When this section is entered, q,

the current trial position for w , is either z , the end of the list

(box 11) , or was set in REMOVE w as the head of the chain directly

above that previously containing w . If q = , then q is the

top of the list and f is updated to be w (boxes 201 and 218) . Otherwise the label of the head of each chain is compared with TES, the

59
label of w , until for some q its label is less than or equal to TES

(boxes 201 through 206). If the label of q is less than TES, then w

becomes the head of a chain containing only itself (boxes 203 and 219

through 225) . If q has the same label as w , then w becomes the

new head of the chain containing q (boxes 204 and 207 through 217)

.

UPDATE f . When the node f is removed from the list (and stored in

v) , it is necessary to find a new f . If the chain containing v had

several nodes, then the new f is the node preceding v in that chain

(boxes 301 and 302) . If v was the only node in the chain, then the new f becomes the last node in the next lower chain. This is accomplished by proceeding down by u (box 303) and across by s (boxes 306

and 307), until the last node in the chain headed by u(v) is found.

Box 305 insures that if v headed a chain, the t pointer for the

first element of the chain below v is set to zero making that chain

the new top chain.

60
S3: SEQUENCE BY LABEL, LINEAR SORT WITH CHAINED TIES

(I)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

f. =

\ 1 z: =

\ t v: = r (C)

UPDATE f

e: = a(v)

AUX: = d(v)

w: = n(e)

TES:=i(e)+AUX

(£>

(21)

(20)

(19)

YES

(18)

END

K5)

INITIALIZATION

d(r) = H(r) = YES

d(v)=oon .- . H(v) = N0j •^^'*'' s(v)= 0, t(v) = 0, u(v) =0.for all v

CONTINUE

STAR LIST (17)

TEM:= d(w)

(ID

(12)

(13)

REMOVE w (o)

y. = 2

H(w): = YES <i>

(b)

ENTER w

/ r

p(w): = V

J i

d(w): =TES

(16)

(15)

^-0

61
REMOVE w

(101)

(102)

(103)

?x: = s(w)

i

q : = t(w)

(121) ^ NO x=0> >-

022)

YES

> [ t(x):«q

(116)

YES» z: = q

(106)

(107)

(108)

(109)

(110)

t(x): =q

( 117) ^

(123)

(124)

y: = q

I

q: = t(y)

t(y): = q

u ( X ) : = y I YES

(112)

> ( F

(III)

Zi = X u(q) : = y

(119)

(113) -> u(q)l = X

(114) y : = X <^

62
ENTER w

(206)

(205)

(204)

(207)

(208)

(210)

(211)

q'. =t(y)

5K

(218)

f '. « w

(219)

u(q)! = w~|--^^?)

YES

R )

< <- y = o> (220)

1 = w I t(y): = w (222)

t(y): = w z . = w (212)

t{w): = q ^

s(w): =

>

' u(w): = y

(223)

(224)

(225)

(213) t(w)! = 1

(214) u(w): * y

(215) I s(w): = q~| ^ t(q): = w~|—

| H(q):=NO| >—(w)

(216) (217)

63
UPDATE f

(301)

(302)

(303)

(304)

(305)

f : = t(f)

f: = u(v)

t(f): =

i\

\ NO

X • . . /x\

T . ~ 5>\r/

(306)

(307)

64
S4: sequencing by labe l, distance list . In this algorithm a node is

placed on the sequence list in a position determined directly by the

value of its label. This algorithm requires one additional piece of

information about the network: MAX, the maximum arc length plus 1. The

sequence list b , which will be called the distance list, has length

MAX. Nodes with equal labels are chained on the sequence list in the

following manner:

b s

^

<^ <—

^4 <- ^

where d, is a label modulo MAX. Rather than actually using modulo

arithmetic, the algorithm keeps track in LEV of the current minimum label

as a multiple of MAX. LEV is incremented by MAX whenever the "read"

pointer z reaches the bottom of the list (boxes 19 and 22) . As for

pointer b , b(y) is the first node of the chain of nodes having label

LEV + y , if y >^ z . Otherwise the node has label LEV + MAX + y . A flag H(v) is used to indicate those nodes v which head chains.

Mapping s points to sucessive nodes in a single chain. For nodes v

which head chains, t(v) is the position in the distance list occupied by

V , and for nodes v which do not head chains t(v) is the node preceding

V in its chain.

S4 proceeds in much the same manner as SI, S2, and S3, Node u is

the one whose forward star is currently being examined (boxes 4 and 17)

it occupies position z in the distance list. If a node w which is

already in the list is encountered, it must be removed from its present

65
position in the list (boxes 11, 12, and a) before it can be added in its new position. The algorithm terminates whenever, after a complete pass

through the distance list, no new nodes have been added to the tree (box

20). The Boolean variable MEM is used to indicate this condition.

REMOVE w . This section of the algorithm removes w from its current

position in the list, prior to inserting it in a new position. If w

does not head a chain, then deleting w involves only updating the s and t pointers (boxes 103 through 105 and 109) . If w heads a chain

then b must be updated, and if there are other elements in the chain

then the old successor of w becomes the new head of the chain (boxes

106 through 109)

.

ENTER w . This section enters w in the correct chain in the list.

Boxes 201 through 203 determine the correct position y in the distance

list, y = TES (mod MAX). Boxes 204 through 211 update the b, s, and t pointers and the Boolean flag H to put w at the head of the chain

of nodes in position y . DELETE u . This section of the algorithm deletes u from the top of

the list. Since u was head of a chain (box 17), if it was the only

node in the chain, then deleting it involves setting b(z): = for the

position z occupied by u (boxes 301 and 302). However, if there

were other nodes in the chain containing u , then the first of them,

s(u), must be made head of the chain (boxes 304 and 305).

66
(I)

(2)

S4: SEQUENCING BY LABEL, DISTANCE LIST

(20)

mem: = NO

lev:

(21) (22)

mem: = NO lev: =lev+max

INITIATE

(23) ( DISTANCE

LIST z

INITIATE

(3)f DISTANCE

LfST z

(19)

CONTINUE

DISTANCE

LIST z ^ ©

(c)

DELETE u (18)

u: = b(z) (17)

*

END

CONTINUE

STAR LIST

(II) <im--(^^> <fEM>TEt>^^ >

INITIATION

d(r)=0

d(v) = GO if V 9^ r

(16) b(z) = 0, I < z < MAX + I H(v) = NO, for oil V

67
REMOVE w

(102) y: = t(w)

(106)

(107)

(103) <^(w)>^^^^»(7)-^rbi"y): ^ X

YES

(201)

(202)

y: « y -MAX

(203)

ENTER w

(206) s(w): * X

(204)

b(y): = w (205)

(207) H(w): =YES

(208) t(w): = y

r:

H(X) : = NO

t

t(!<): = w

(211)

(210)

(209)

68
DELETE u

(303)

9

(301) v: = s(u)

\f (302) b(z): = v

(304)

(305)

This work has greatly profited from continual discussions with the

staff of the Operations Research Section of the National Bureau of

Standards. In addition. Dr. Bernard M. Levin of the National Bureau of

Standards made his extensive bibliography available during the early

stages of the work. Valuable insight was gained from experiments

conducted and communicated by C.T. Zahn, Jr. The use of binary tree

sorting was suggested by E. McCreight. The work was started under the

support of the United States Post Office (the Office of Research and

Engineering), and parts were also supported by the United States Department of Transportation (Northeast Corridor Transportation Project).

Our thanks for excellent typing go to Mrs. Dolores E. Harrison.

69
10. REFERENCES

[I] Bellman, R. , On a routing problem, Quart. Appl. Math. 16^, 87-90

(1958).

[2] Bellman, R. , and R. Kalaba., On k— best policies, J. Soc. Indust.

Appl. Math. 8, 582-588 (1960).

[3] Bentley, D.L., and Kenneth L. Cooke, Convergence of successive

approximations in the shortest route problem, J. Math. Anal. Appl.

10, 269-274 (1965).

[4] Berge, C, Theorie des graphes et ses applications, Dunod, Paris,

(1958).

Translated, Theory of graphs and its applications, Methuen, London,

(1962).

[5] Bock, F., H. Kantner, and J. Haynes, An algorithm (the r— best

path algorithm) for finding and ranking paths through a network,

(1957) Research report, ARMOUR RESEAJICH FOUNDATION, Technology

Center, Chicago, 111.

[6] Clarke, S., A. Krikorian, and J. Rausen, Computing the N best

loopless paths in a network, J. Soc. Indust. Appl. Math. 11 , 1096-1102 (1963).

[7] Dantzig, G.B., On the shortest route through a network. Management

Sci. 6, 187-190 (1960).

[8] , Discrete-variable extremum problems. Operations Res. 5^, 268-273 (1957).

[9] , All shortest routes in a graph. Operations Res. House,

Stanford University, Technical Report No. 66-3, November (1966).

[10] Dial, Robert B., Algorithm 360 Shortest path forest with topological ordering [H], Comm. ACM 12^, 632-633 (1969).

[II] Dijkstra, E.W., A note on two problems in connexion with graphs,

Numer. Math 1, 269-271 (1959).

[12] Dreyfus, Stuart E. , An appraisal of some shortest-path algorithms,

Operations Res. 17^, 395-412 (1969).

[13] Farbey, B.A., A.H. Land, and J.D. Murchland, The Cascade Algorithm

for finding all shortest distances in a directed graph. Management

Science 14, 19-28 (1967).

[14] Floyd, R.W., "Algorithm 97, shortest path", Comm. ACM, 5_, 345

(1962).

70
[15] Ford, L.R., Jr., and D.R. Fulkerson, Flows in networks, Princeton

University Press, Princeton, (1962).

[16] Fulkerson, D.R., Flow networks and combinatorial operations

research, Amer. Math. Monthly, 73, 115-138 (1966).

[17] Foulkes, J.D., W. Prager, and W.H. Warner, On bus schedules.

Management Science 1^ 41-48, (Oct. 1954).

[18] Goldman, A.J., and Christoph Witzgall, Most profitable routing

before maintenance, abstracted in Bulletin of Operations Res.

Soc. of Am., Operations Res., _13 supplement 1, B-82 (1965).

[19] Hardgrave, W.W. , and G.L. Nemhauser, On the relation between the

traveling salesman and the longest path problems. Operations Res.

10, 647-657 (1962).

[20] Hart, Peter E., Nils J. Nilsson, and Bertram Raphael, A formal

basis for the heuristic determination of minimum cost paths IEEE

Transactions of Systems Science and Cybernetics SSC-4 ) .100-107

(1968).

[21] Hitchner, Lewis E., A comparative investigation of the computational efficiency of shortest path algorithms. Report ORG 68-25,

Operations Research Center, University of California, Berkley

(1968).

[22] Hoffman, W. , and R. Pavley, Applications of digital computers to

problems in the study of vehicular traffic, Proc. Western Joint

Computer Conf., 159-161 (May 1958).

[23] , A method for the solution of the n— best path problem,

J. Assoc. Comput. Mach. 6, 506-514 (1959).

[24 Hu, T.C., Revised matrix algorithms for shortest paths, SIAM

J. Appl. Math. 15, 207-218 (1967).

[25] , A decomposition algorithm for shortest paths in a network. Operations Res. ^, 91-102 (1968).

[26] , Integer programming and network flows, Addison-Wesley,

Reading, Mass. (1969).

[27] Hu, T.C. and W.T. Torres, Shortcut in the decomposition algorithm

for shortest paths in a network, IBM J. of Res. Develop., 387-390

(1969).

[28] Johnson, E.L., Networks and basic solutions, Operations Res. 14 , 619-623 (1966).

71
[29] Klee, V., A "string algorithm" for shortest path in directed networks, Operations Res. 1^, 428-432 (1964).

[30] Knuth, Donald E. , The art of computer programming, Vol.1,

Fundamental algorithms, Addison-Wesley , Reading, Mass., 305-406

(1968).

[31] Land, A.H. and S.W. Stairs, The extension of the cascade algorithm

to large graphs, Management Science 14^, 29-33 (1967).

[32] Levin, B.M., and S. Hedetniemi, Determining fastest routes using

fixed schedules, Spring Joint Computer Conference (1963).

[33] Loubal, Peter, A network evaluation procedure. Highway Research

Record 205, 96-109 (1967).

[34] Luccio, F., On some iterative methods for the determination of

optimal paths through a network, Calcolo 3^, 31-48 (1966)

.

[35] Martin, B.V., Minimum path algorithms for transportation planning,

MIT, Dept. of Civil Engineering, Highway Transportation Project

(1963).

[36] McCarthy, J.,et. al., LISP 1.5 Programmer's Manual, MIT Press,

Cambridge, Mass. (1962).

[37] Mickle, Marlin, Tsung-Wei Sze, and Donald E. Rathbone, Neighborhood Storage, IEEE Transactions of Systems Science and Cybernetics

SSC-4 , 138-144 (1968).

[38] Mills, G., A decomposition algorithm for the shortest route

problem. Operations Res. 14, 279-291 (1966).

[39] Minty, G.J., A comment on the shortest-route problem. Operations

Res. 5^, 724 (1957).

[40] , A variant on the shortest-route problem. Operations Res. 6_, 882 (1958).

[41] Moore, E.F., The shortest path through a maze. Proceedings of an international symposium on the theory of switching ,. Part II, April

2-5 (1957), The Annals of the Computation Laboratory of Harvard

University ^, Harvard University Press (1959)

.

[42] Murchland, J.B., The shortest-route problem-An addendum, Operations

Res. 9, 129-132 (1961).

72
Nemhauser, George L., A generalized permanent label setting algorithm for the shortest path between specified nodes, J. of Math.

Appl. 38, 328-334 (1972).

Nicholson, T.A.J. , Finding the shortest route between two points

in a network, Computer J. 9^, 27-5-280 (1966).

Pandit, S.N.N. , A new matrix calculus, J. Soc. Indus t. Appl. Math,

9_, 632-639 (1961).

, Some observations on the routing problem. Operations Res.

10, 726 (1962)

, Some observations on the longest path problem, Operations

Res. 12, 361-364 (1964).

Peart, R.M., P.H. Randolf, and T.E. Bartlett, The shortest-route

problem. Operations Res. 8^, 866-868 (1960).

Pollack, M. , The maximum capacity through a network. Operations

Res. 8, 733-736 (1960).

, The k— best route through a network. Operations Res. 9_, 578-580 (1961).

t"Vi

, Solutions of the k— best route through a networka review, J. Math. Anal. Appl. ^, 547-599 (1961).

Pollack, M. , and W. Wiebenson., Solutions of the shortest-route

problem-a review. Operations Res. 8^, 224-230 (1960).

> Comments on "the shortest-route

problem" by Peart, Randolph, and Bartlett, Operations Res. %

411-412 (1961).

Sakarovitch, M. , The k shortest routes and the k shortest chains

in a graph. Operations Research Center, University of California,

Berkley, Report ORC 66-32 (1966).

Saksena, J. P. and Santosk Kumar, The routing problem with 'K' specified nodes. Operations Res. 14, 909-913 (1966).

Scions, H.I., The compact representation of a rooted tree and the

Transportation Problem, Internat. Symp. on Math. Programming,

London, (1964)

Shimbel, A., Structure in communication nets. Proceedings of the

Symposium on Information Networks, N.Y., Brooklyn Polytechnic

Institute (1954)

73
[58] Suurballe, J.W., Network algorithms, International Research Institute, Box 302, Far Hills, N.J.

[59] Traffic assignment manual for applications with a large, highspeed computer, U.S. Department of Commerce, Bureau of Public

Roads, Office of Planning, Urban Planning Division (1964).

[60] Weimer, D.L., A serial technique to determine minimum paths,

Comm. ACM 6^, 663-665 (1963).

[61] Whiting, P.D-* and J. A. Hillier, A method for finding the shortest

route through a road network. Operational Research Quarterly, 11 , 37-40 (1960).

[62] Yaged, B., Traffic flow information for minimum cost routing

procedures, Automatica 5^, 167-173 (1969).

74
APPENDIX

FORTRAN PROGRAMS FOR SEVEN LABELING SHORTEST PATH ALGORITHMS

This appendix contains listings of FORTRAN programs. for the seven

labeling algorithms upon which the experiments described in section 7 were performed. The programs have been included both to fully document

the experimental runs and to provide programs for readers who need to use a shortest path algorithm. Copies of the FORTRAN card decks may be

obtained from:

Judith Gilsinn

Operations Research Section, Applied

Mathematics Division

Room 428, Administration Building

National Bureau of Standards

Washington, D.C. 20234

Input and output routines have not been included in this appendix,

since they are much more machine-and user-dependent than the algorithms.

The programs listed here utilize BLANK COMMON to pass data to and from

the algorithms. The arrays A, N, and L (corresponding to a, n, and £

in the text) together with the variables NODE, the number of nodes,

LINK, the number of arcs, and MAX, one plus the maximum arc length,

contain the network description. The algorithm then calculates the tree

rooted at R (corresponding to r) and stores it in the arrays D and

P (corresponding to d and p in the text)

»

75
SUBKOUTINr ci

COMMON N( fOOOO) .L( 10000) ,0(3900) iP ( 3900 )|A( 3900). R»

1 NOr>E .LINK ,MAX ,T ( HOOO)

INTEGER A.P.D iR »V ,AUX ,E .W.TES

LOGICAL T.MEM

C INlTlALlZATinN

DO 6 V«l .VODE

P(V)«0

D( V

)

«999909999

T( V)«.FAL«^E.

6 CONTINUE

D(R)«0

T tR)*,TRUr , C START ALGORITHM

7 MEM».FALSP,

DO 10 V«1*,N00E

IF ( .NOT.T ( V ) ) GO TO 10

AUX*D( V)

IOO*N«A ( V ) IF (IDOWN.EQ.O) GO TO 9

M«V + l 71 1UP«A (M)-l

IF ( lUP.GT.-l ) GO TO 72

MsM+1

GO TO 7 1 72 DO 8 E«ID<^WN,IUP

WaN(E ) T E S L < E ) + A U X IF ITES.Gr.OdW) ) GO TO 8

D ( W ) T E S

P(i^)«V

T(W)».TRUF,

MEMsfTRUE.

8 CONT INUE

9 T( V)«,FAL«5E.

10 CONTINUE

IF (MEM) r,o TO 7 RETURN

END

76
10

1

SUBKOUTINr C2

COMMON N( 'GOOO), L(IOOOO), 0(3900). P(39 00 )«A( 3900)

1 f^Of^E .LINK »MAX ,T(4000) ,S( HOOO)

INTEGER «.P.D,R,V.U,AUX,e,W,TES,B,Z

LOGICAL T INITIALIZATION

DO 6 Vs 1 j^'OOt

P( V)«0

T( V)».FAL«;E,

( V ) »9f 99<»999'?

CONTINUE

D(R)«0

START ALGORITHM

V«l

Z«V

U»R

AUX»0(U)

lOOWN.A (U ) IF (IDOKIN.EQ.O) GO TO 1 1 M«U*l

iUP«A(M)-i

IF ( IUP.GT,-i ) GO TO 9

M«M+ 1 GO TO 8

DO 10 Esir^OAN , I UP

W»N{E)

TES*L(E )+AUX

IF (D(W) .r E.TES) 60 TO 10

D( VV)«TES

P ( * ) « U

IF(T(W))G0TO10

T ( W)a. TRUr

,

B(Z )«y.

Z«Z+l

IF (Z.GT.MODE) Z»l

CONTINUE

IF (V,EQ.7) RETURN

U=B(V)

T(U)»,FAL«tE.

v*y + i IF (V.GTt^iODE) V«l

60 TO 7 END

77
SUBROUTINr Ci

COMMON N(?OOO0),L(l00O0>.D(39O0)tP(390O»iA(39O0).R.

I NHDE.tlNK.MAX ,F(HOOO) ,G( HQOO) ,8(M000) ,H(HOOO)

INTtGER A,P,0,R.V,F.G,E,A.TES.AUX,X,DEL,T,S

LOGICAL o.H.MEM

00 1 V=l ,^'ODE

D ( V

)

«9999P9999

P ( V )«0

2

20

3

C

6

B

GO TO 12

GO TO 1

1

M

B( v) = .f'al«;e,

H( V )«.FAL«?E.

CONTINUE

[)(R)sO

F (R )»R

H{R)s,TRUr,

V»R

MEM=.FALSr,

IF ( .NOT.Mj V ) ) AUX»D( V ) IDOWNsA ( V ) IF (lDO*N.EQ.O)

I bv* I iup»Af n-t

IF ( IUP.GT,-1 ) GO T

1 = 1 + 1 60 TO 3

DO 10 Etlf^OWNiIUP

W»N(E ) TES«L(E)+«UX

X*W

IF (D(W) f'^E, 999999999)

DELaD(W)-TES

IF (DEL. LP, 0) GO TO 10

SEVER

D(X Ja.TRUr,

T»F(X)

IF (T.EQ.P) GO

I»P(T)

IF < .NOT." ( I) r 0{T)=D{T )-DEL

H(T)«,TRUr,

XsT

GO TO 6

SbG( W ) F{S)«T

G(T>«S

T«W

B(T)«,FAL«!E.

IF (T«EQ.y ) T«F(T)

GO TO 8

GO TO 9

10

TO 7

GO TO 7

GO TO 9

78
i

f

C ATTACH

9 S«F (V ) F(X)«S

G{S)*X

F { V)«W

G( W> «V

P ( A )«V

D(*)sTES

H(W)*,TRUP,

MEMS. TRUE,

IC CONTINUE

1 I H( V)c,fAL«:E,

12 V«G(V)

IF (V.NE.P)

IF (MEM) CO

RETURN

END

GO

TO

TO

2

20

79

il
IC

1

1

12

1 3

SUBKOUTINT Si

COMMON N( 1 0000) .L( lOOOO) |0(39Q0) iP(3900) |A{3900) .R.

1 NOf^E .LINK , MAX ,B(M000) ,T ('OOOi

INTLGtR A,P,D,R,V,Z.S,U,X,Y,AUX,TeM.TES,E»W.B.T

INITIALIZATION

DO 6 V=l .MODE

P( V )«0

D ( V

)

»999909999

CONT INUE

D(K )*0

START ALGORITHM

B(Z)«R

SeZ

T(R)«Z

UsB(S 5 IDOWNsA (U

)

IF ( IDOWN.EQ.O) GO TO 15

AUX = D(U ) I«U+1

lUPsA ( I )-!

IF ( luP.GT.-i 1 GO TO 9

I«I + l 60 TO 8

DO 14 EsinoWN.IUP

W«N ( E ) TESsLlE )*AUX

T E M = D ^ W ) IF ( TEM.GF .999999999 ) GO TO 10

IF (TEM.Lr.TES) GO TO 1 M 60 TO 11

Z«Z*1

B { Z ) « yv T(W)=Z

D{ W)=TE5

P ( W) =U

SORT

Y«T ( W ) X»Y

Y*Y-1

V=B{Y)

IF (D( V) .( E.TES) GO TO 13

B ( X )«V

T ( V )=X

GO TO 12

B ( X )«W

T { W ) * X CONT INUE

IF (S,EQ»7) RETURN

5 = S+1

GO TO 7 END

80
6

9

10

SUBKOUTINF S2

COMMON N ( tOOOO ), L ( 10000) |0( 3900 )»P( 3900 )|A< 3900). R.

I N0f>E,LlNK ,MaX ,B(MO00) ,7 (HOOO)

INTEGER f.P,TES.2.A,H,Q,S.U,AUX,R,T,V,B.T£M,iiy.0.TEM,Y

INITIALIZATION

DO I V s 1 . »'' D

PI V )=0

IF ( V.EQ.P ) GO TO 1 D ( V ) » 9 9 9 9 o 9 9 9 9

CONT INUE

D (R )«0

START ALGORITHM

Zal

UaR

IDOWNsA (U)

IF (IDOWN.EQ.O) GO TO 10

AUX=D(U)

I«U*1

IUP«A( I )-1

IF ( lUP.GT.-i ) GO TO M 1*1 + 1 GO TO 3

DO 9 E=IDnwN,IUP

WxN(E)

TES«L (E )+AUX

TEMaDjW)

IF (TEM.LT, 999999999) 60 TO 5

S«2

Z«Z+1

60 TO 6

IF (TEM.LF.TES) 60 TO 9

S»T(W)

0(W)«TES

p ( yv )«u

SIFT UP

HxS/2

IF (H.LEt") GO TO 8

V»B (H ) TEM*D( V)

IF (TEM,Lr,TES) GO TO 8

B(S)=V

T( V)sS

S«H

GO TO 7 B(S)»IAI

T ( W )*S

CONTINUE

ZsZ-1

IF (Z.EQ.H) RETURN

Q«B(Z)

UsB( 1 )

81
1

1

SIFT 00»^N

TES*D(Q)

12

13

H«S»2

IF (H,GE.7) (sO

V«B(H)

TEM»D( V ) K

TO 13

K«H+1

IF (K.GE.7) GO TO 12

YsB(K)

TEN«D ( Y ) IF (TEN.GF.TEM) 60 TO 12

TEM«TEN

VaY

IF (TES.LT.TEM)

B (S)«V

T ( V 1=5

S«H

GO TO 11

B(S)sQ

T(«)sS

GO TO 2 END

GO TO 13

82
SUBKOUTINr S3

COMMON N(tOOOO).L{ 10000) •0(39QC)iP(3900)iA(3900).R,

I N^DE,LInK,MAX,5(M000) ,T(MOO0) ,U<MOOO) ,H(«*000)

INTEGER r.P.TET,Y.F,Q,S,U.Z.A.R,T.V.AUX,TEM,w.O,TES.X

LOGICAL M

001V»l»^iODE

D ( V ) «9999«>9999

P( V )«0

H( V)«.FAL*;F.

S( V )sO

T(V)*0

U( V )«0

CONTINUE

D(R)aO

H(R)«,TRUF,

F«0

ZsO

V«R

IDOWNeA(Vl

IF (IDOWN,EQ.O) GO TO 22

AUX=0( V)

I«V*1

IUP=A ( I )-l

IF ( lUP.GT.-i ) 60 TO H I«I*1

GO TO 3

DO 21 E»I^0WN,IUP

W=N{E

TES»L(E)*AUX

TEMbD( W)

IF ( TEM.LT, 999999999) 60 TO 5

Q«Z

YsO

H ( ifl/ ) = , T R U r , GO TO 13

IF (TEM.LT, TES) GO TO 21

REMOVE W

X«S(W)

QaT ( W

IF (H(W) ) GO TO 7

S{Q)sX

IF (X.NiE.") T»X)«Q

YaQ

Q«T(Y)

IF { .hOT.M( Y) r GO TO 6

H(W)«,TRUF,

GO TO 13

83
ID

1 1 12

C

13

1*4

2*4

25

26

15

16

17

18

19

Y * U ( A ) IF (X.EQ.'^l 0,0 TO 10

H( X )«.TRUr , T(X)*a

U( X )sY

IF (Y.EQ.^) GO TO 8

T

(

Y)«X

CsO TO 9

z«x

IF (Q,NE.^) U(Q )«X

Y«X

GO TO 13

IF ( Y.EQ.«) GO TO 11

T(Y)«Q

G T 1 2

Z»Q

IF (Q.NE.'^) utQ)«Y

ENTER W

IF (Q.EQ.n) GO TO 15

TET«D (Q ) IF (TET.LT.TES) GO TO

IF (TET.En.TES) GO TO

YxQ'

Q«T( Y ) GO TO 13

I»T(Q)

IF (I.N^Et*^) U(I)«W

IF (Y.EQ.H) GO TO 25

T ( Y ) « ft GO TO 26

Z«W

T(W)»I

U(W)*Y

T{Q)«W

H(Q)«,FAL«?E.

GO TO 20

F«ify

GO TO 17

IF (Y.EQ.'^) CO TO 18

T( Y )*W

60 TO 19

z«w

T ( * )«0

S(* )«0

U { * ) Y

16

IM

84
^

20 0(W)»TES

21 CONTINUE

22 IF (F.EQ.n) RETURN

V-F

IF (V.EQ»7) Z.O

FaTtF)

IF (F,NE.«^) GO TO 2

F«U(V)

IF (F.EQ.") 60 TO 2

T(F)«0

23 IF (S(F) .FQ.O) GO TO 2

FeS(F)

60 TO 23

END

85
I

SUBROUTINE SM

COMMON N{»0000) .LdOOOO) ,0(3900) .P(3900) .A (3900 » .R.

NODE.LINK.MAX.S(MOOO).T(MOOO).B(MOOO).H(*4000)

INTEGER r.TE5.Y,A.U.Z.AUX,P,S.V,B.R.T.W.D,TEM.X

LOGICAL MEM.H

00 I Usli'^'ODE

D ( U ) »999909999

H ( U ) « • f A L «^ E . S(Ul SO

T (U)*0

P (U)«0

1 CONTINUE

D(R)=0

DO 2 Z»I i^AX

B(Z)«0

2 CONTINUE

C START ALGORITHM

MEM*.FALSr.

LEV»0

Z«l

U«R

3 IDOWN=A(U)

IF (lOOWN.EQ.O) GO TO 13

AUX»D(U)

I«U+l

H lUPaA ( I ) -1

IF ( IUPt6T,-l ) GO TO 5

I»I*1

60 TO *4 5 DO 12 E«inoWN,IUP

W»N(E)

TES«L(E)*AUX

TEM«0(W)

IF (TEM.GF,999999999) 60 TO B IF (TEM.LftTES) GO TO 12

C REMOVE W

X.S(W)

Y«T (W)

IF (H(W) ) GO TO 6

SIY)=X

IF (X.NEt") GO TO 7

GO TO 8

6 B(Y J*X

IF (X.EQ.*^) GO TO 8

H(X)«.TRUr,

7 T(X)«Y

86
10

11

12

13

C

IS

E N T F. R Y«

IF

Y«

GO

Xa

B(

S(

H(

T(

IF

T(

H(

D(

P(

CO

U«

IF

Z«

IF

IF

ME

LE

Zb

60

OELET

V«

B(

IF

T(

H<

GO

EN

A TES

(Y

Y-M

TO

B(Y

Y)«

W)«

A) * tt)«

(X

X)«

X)«

W)«

M«.

NTI

B(Z

(U

Z*l

(Z

(«

M«»

V»L

1 TO

E U

S(U

Z)«

(V

V)«

V)«

TO

D

-LEV

•LE.MAX) GO TO 10

AX

9

)

X.TRUr,

Y

• EQ.H) GO TO 1 I .FALSE.

TES

U

TRUE,

NUE

).NE.o) GO TO \H

.LE.*^AX) 60 TO 13

NOT. MEM) RETURN

FALSr,

EV + MA X

13

)V.EQ.H) GO TO 3

Z.TRUr,

3

ft U. S. GOVERNMENT PRINTING OFFICE : 1973--511-325/242

87
.FORM NBS-114A (1-71) 12. Gov't Accesslcn No.

U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO. NBS TN-7723. Recipient's Accession No.

4. TITLE AND SUBTITLE

A Performance Comparison of Labeling Algorithms for

Calculating Shortest Path Trees

5. Publication Date May 1973

6. Performing Or^nization Code

7. AUTHOR(S)

Judith Gilsinn and Christoph Witzgall

8. Performing Organizanon

10. Project/Task/Work Unit No. 2050152

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

11. Contract/Grant No.

12. Sponsoring Organization Name and Address

Same as No.

9

13. Type of Report & Period Covered Final

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant

bibliography or literature survey, mention it here.)

Many applications in transportation and commvinication require the

calculation of shortest routes between points in a network, and several

algorithms for the solution of this problem exist in the literature.

This paper examines one class of such algorithms, that which calculates

a shortest route from one point in the network to all other intersection

points. Computer data handling techniques which can be used to improve

the two basic algorithms in this class are investigated. Results of

computer timing runs on various types and sizes of networks are compared,

and the differences, sometimes of an order of magnitude, are analyzed.

Detailed flowcharts and computer programs of the tested algorithms are

also included.

17. KEY WORDS (Alphabetical order, separated by semicolons)

Algorithms; networks; paths; shortest-paths; trees.

18. AVAILABILITY STATEMENT

fxl UNLIMITED.

I I FOR OFFICIAL DISTRIBUTION. DO NOT RELEASE

TO NTIS.

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF PAGES

92

22. Price

$1.25 Domestic postpaid $1.00 G. P.O. Bookstore

USQi>MM-DC 66244.P71
NBS TECHNICAL PUBLICATIONS

PERIODICALS JOURNAL OF RESEARCH reports National Bureau of Standards research and development in

physics, mathematics, and chemistry. Comprehensive

scientific papers give complete details of the work,

including laboratory data, experimental procedures,

and theoretical and mathematical analyses. Illustrated with photographs, drawings, and charts. Includes

listings of other NBS papers as issued.

Published in two sections, available separately:

• Physics and Chemistry (Section A)

Papers of interest primarily to scientists working in these fields. This section covers a broad range of physical and chemical research, with major emphasis on standards of physical measurement, fundamental

constants, and properties of matter. Issued six times

a year. Annual subscription: Domestic, $17.00; Foreign, $21.25.

• Mathematical Sciences (Section B)

Studies and compilations designed mainly for the mathematician and theoretical physicist. Topics in mathematical statistics, theory of experiment design,

numerical analysis, theoretical physics and chemistry,

logical design and programming of computers and

computer systems. Short numerical tables. Issued quarterly. Annual subscription: Domestic, $9.00; Foreign,

$11.25.

TECHNICAL NEWS BULLETIN

The best single source of information concerning the Bureau's measurement, research, developmental, cooperative, and publication activities, this monthly

publication is designed for the industry-oriented

individual whose daily work involves intimate contact with science and technology—/or engineers, chemists,

physicists, research managers, product-development

managers, and company executives. Includes listing of

all NBS papers as issued. Annual subscription : Domestic, $6.50; Foreign, $8.25.

NONPERIODICALS Applied Mathematics Series. Mathematical tables, manuals, and studies. Building Science Series. Research results, test methods, and performance criteria of building materials, components, systems, and structures. Handbooks. Recommended codes of engineering

and industrial practice (including safety codes) de- veloped in cooperation with interested industries, professional organizations, and regulatory bodies. Special Publications. Proceedings of NBS conferences, bibliographies, annual reports, wall charts, pamphlets, etc. Monographs. Major contributions to the technical

literature on various subjects related to the Bureau's

scientific and technical activities. National Standard Reference Data Series.

NSRDS provides quantitative data on the physical

and chemical properties of materials, compiled from

the world's literature and critically evaluated. Product Standards. Provide requirements for sizes, types, quality, and methods for testing various industrial products. , These standards are developed co- operatively with interested Government and industry groups and provide the basis for common understanding of product characteristics for both buyers and

sellers. Their use is voluntary.

Technical Notes. This series consists of communications and reports (covering both other-agency and

NBS-sponsored work) of limited or transitory interest. Federal Information Processing Standards

Publications. This series is the official publication within the Federal Government for information on

standards adopted and promulgated under the Public Law 89—306, and Bureau of the Budget Circular A—86

entitled. Standardization of Data Elements and Codes

in Data Systems.

Consumer Information Series. Practical information, based on NBS research and experience, covering areas of interest to the consumer. Easily understandable language and illustrations provide useful background knowledge for shopping in today's tech- nological marketplace.

BIBLIOGRAPHIC SUBSCRIPTION SERVICES

The following current-awareness and literature-survey bibliographies are issued periodically by the Bureau:

Cryogenic Data Center Current Awareness Service ( Publications and Reports of Interest in Cryogenics)

A literature survey issued weekly. Annual subscription: Domestic, $20.00; foreign, $25.00.

Liquefied Natural Gas. A literature survey issued quarterly. Annual subscription: $20.00. Superconducting Devices and Materials. A literature survey issued quarterly. Annual subscription: $20,00. Send subscription orders and remittances for the preceding bibliographic services to the U,S, Department

of Commerce, National Technical Information Service, Springfield, Va. 22151. Electromagnetic Metrology Current Awareness Service (Abstracts of Selected Articles on Measurement

Techniques and Standards of Electromagnetic Quantities from D-C to Millimeter-Wave Frequencies), Issued monthly. Annual subscription: $100.00 (Special rates for multi-subscriptions). Send subscription order and

remittance to the Electromagnetic Metrology Information Center, Electromagnetics Division, National Bureau

of Standards, Boulder, Colo. 80302. Order NBS publications (except Bibliographic Subscription Services)

from : Superintendent of Documents, Government Printing Oflice, Washington, D.C. 20402.
U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Washington. D.C. 20234

OFFICIAL BUSINESS

Penalty for Private Use, $300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE

COM-215