On the History of the Shortest Path Problem

Alexander Schrijver

2010 Mathematics Subject Classification: 01A60, 05-03, 05C38, 05C85, 90C27 Keywords and Phrases: Shortest path, algorithm, history

It is difficult to trace back the history of the shortest path problem. One can imagine that even in very primitive (even animal) societies, finding short paths (for instance, to food) is essential. Compared with other combinatorial optimization problems, like shortest spanning tree, assignment and transportation, the mathematical research in the shortest path problem started relatively late. This might be due to the fact that the problem is elementary and relatively easy, which is also illustrated by the fact that at the moment that the problem came into the focus of interest, several researchers independently developed similar methods.

Yet, the problem has offered some substantial difficulties. For some considerable period heuristical, nonoptimal approaches have been investigated (cf. for instance Rosenfeld [1956], who gave a heuristic approach for determining an optimal trucking route through a given traffic congestion pattern).

Path finding, in particular searching in a maze, belongs to the classical graph problems, and the classical references are Wiener [1873], Lucas [1882] (describing a method due to C.P. Trémaux), and Tarry [1895] – see Biggs, Lloyd, and Wilson [1976]. They form the basis for depth-first search techniques.

Path problems were also studied at the beginning of the 1950’s in the context of ‘alternate routing’, that is, finding a second shortest route if the shortest route is blocked. This applies to freeway usage (Trueblood [1952]), but also to telephone call routing. At that time making long-distance calls in the U.S.A. was automatized, and alternate routes for telephone calls over the U.S. telephone network nation-wide should be found automatically. Quoting Jacobitti [1955]:

When a telephone customer makes a long-distance call, the major problem facing the operator is how to get the call to its destination. In some cases, each toll operator has two main routes by which the call can be started towards this destination. The first-choice route, of course, is the most direct route. If this is busy, the second choice is made, followed by other available choices at the operator’s discretion. When telephone operators are concerned with such a call, they can exercise choice between alternate routes. But when operator or customer toll dialing is considered, the choice of routes has to be left to a machine. Since the “intelligence” of a machine is limited to previously “programmed” operations, the choice of routes has to be decided upon, and incorporated in, an automatic alternate routing arrangement.

Matrix methods for unit-length shortest path 1946–1953

Matrix methods were developed to study relations in networks, like finding the transitive closure of a relation; that is, identifying in a directed graph the pairs of points s, t such that t is reachable from s. Such methods were studied because of their application to communication nets (including neural nets) and to animal sociology (e.g. peck rights).

The matrix methods consist of representing the directed graph by a matrix, and then taking iterative matrix products to calculate the transitive closure. This was studied by Landahl and Runge [1946], Landahl [1947], Luce and Perry [1949], Luce [1950], Lunts [1950, 1952], and by A. Shimbel.

Shimbel’s interest in matrix methods was motivated by their applications to neural networks. He analyzed with matrices which sites in a network can communicate to each other, and how much time it takes. To this end, let S be the 0, 1 matrix indicating that if S_{i,j} = 1 then there is direct communication from i to j (including i = j). Shimbel [1951] observed that the positive entries in S^{t} correspond to pairs between which there exists communication in t steps. An adequate communication system is one for which the matrix S^{t} is positive for some t. One of the other observations of Shimbel [1951] is that in an adequate communication system, the time it takes that all sites have all information, is equal to the minimum value of t for which S^{t} is positive. (A related phenomenon was observed by Luce [1950].)

Shimbel [1953] mentioned that the distance from i to j is equal to the number of zeros in the i, j position in the matrices S^{0}, S^{1}, S^{2}, …, S^{t}. So essentially he gave an O(n^{4}) algorithm to find all distances in a directed graph with unit lengths.

Shortest-length paths

If a directed graph D = (V, A) and a length function l : A → ℝ are given, one may ask for the distances and shortest-length paths from a given vertex s.

For this, there are two well-known methods: the ‘Bellman-Ford method’ and ‘Dijkstra’s method’. The latter one is faster but is restricted to nonnegative length functions. The former method only requires that there is no directed circuit of negative length.

The general framework for both methods is the following scheme, described in this general form by Ford [1956]. Keep a provisional distance function d.

Initially, set d(s) := 0 and d(v) := ∞ for each v ≠ s. Next, iteratively,

choose an arc (u, v) with d(v) > d(u) + l(u, v) and reset d(v) := d(u) + l(u, v).

(1)

If no such arc exists, d is the distance function.

The difference in the methods is the rule by which the arc (u, v) with d(v) > d(u) + l(u, v) is chosen. The Bellman-Ford method consists of considering all arcs consecutively and applying (1) where possible, and repeating this (at most |V | rounds suffice). This is the method described by Shimbel [1955], Bellman [1958], and Moore [1959].

Dijkstra’s method prescribes to choose an arc (u, v) with d(u) smallest (then each arc is chosen at most once, if the lengths are nonnegative). This was described by Leyzorek, Gray, Johnson, Ladew, Meaker, Petry, and Seitz [1957] and Dijkstra [1959]. A related method, but slightly slower than Dijkstra’s method when implemented, was given by Dantzig [1958], and chooses an arc (u, v) with d(u) + l(u, v) smallest.

Parallel to this, a number of further results were obtained on the shortest path problem, including a linear programming approach and ‘good characterizations’. We review the articles in a more or less chronological order.

Shimbel 1955

The paper of Shimbel [1955] was presented in April 1954 at the Symposium on Information Networks in New York. Extending his matrix methods for unit-length shortest paths, he introduced the following ‘min-sum algebra’:

\underline{Arithmetic}

For any arbitrary real or infinite numbers x and y

x + y ≡ min(x, y) and

xy ≡ the algebraic sum of x and y.

He transferred this arithmetic to the matrix product. Calling the distance matrix associated with a given length matrix S the ‘dispersion’, he stated:

It follows trivially that S^{k} k ≥ 1 is a matrix giving the \underline{shortest} paths from site to site in S given that k − 1 \underline{other} sites may be traversed in the process. It also follows that for any S there exists an integer k such that S^{k} = S^{k+1}. Clearly, the dispersion of S (let us label it D(S)) will be the matrix S^{k} such that S^{k} = S^{k+1}.

This is equivalent to the Bellman-Ford method.

Although Shimbel did not mention it, one trivially can take k ≤ |V |, and hence the method yields an O(n^{4}) algorithm to find the distances between all pairs of points.

1 Shortest path as linear programming problem 1955–1957

Orden [1955] observed that the shortest path problem is a special case of a transshipment problem (= uncapacitated minimum-cost flow problem), and hence can be solved by linear programming. Dantzig [1957] described the following graphical procedure for the simplex method applied to this problem. Let T be a rooted spanning tree on {1, …, n}, with root 1. For each i = 1, …, n, let u_{i} be equal to the length of the path from 1 to i in T. Now if u_{j} ≤ u_{i} + d_{i,j} for all i, j, then for each i, the 1 − i path in T is a shortest path. If u_{j} > u_{i} + d_{i,j}, replace the arc of T entering j by the arc (i, j), and iterate with the new tree.

Trivially, this process terminates (as ∑_{j=1}^{n} u_{j} decreases at each iteration, and as there are only finitely many rooted trees). Dantzig illustrated his method by an example of sending a package from Los Angeles to Boston. (Edmonds [1970] showed that this method may take exponential time.)

In a reaction to the paper of Dantzig [1957], Minty [1957] proposed an ‘analog computer’ for the shortest path problem:

Build a string model of the travel network, where knots represent cities and string lengths represent distances (or costs). Seize the knot ‘Los Angeles’ in your left hand and the knot ‘Boston’ in your right and pull them apart. If the model becomes entangled, have an assistant untie and re-tie knots until the entanglement is resolved. Eventually one or more paths will stretch tight – they then are alternative shortest routes.

Dantzig’s ‘shortest-route tree’ can be found in this model by weighting the knots and picking up the model by the knot ‘Los Angeles’.

It is well to label the knots since after one or two uses of the model their identities are easily confused.

A similar method was proposed by Bock and Cameron [1958].

Ford 1956

In a RAND report dated 14 August 1956, Ford [1956] described a method to find a shortest path from P_{0} to P_{N}, in a network with vertices P_{0}, …, P_{N}, where l_{ij} denotes the length of an arc from i to j. We quote:

Assign initially x_{0} = 0 and x_{i} = ∞ for i ≠ 0. Scan the network for a pair P_{i} and P_{j} with the property that x_{i} − x_{j} > l_{ji}. For this pair replace x_{i} by x_{j} + l_{ji}. Continue this process. Eventually no such pairs can be found, and x_{N} is now minimal and represents the minimal distance from P_{0} to P_{N}.

So this is the general scheme described above (1). No selection rule for the arc (u, v) in (1) is prescribed by Ford.

Ford showed that the method terminates. It was shown however by Johnson [1973a, 1973b, 1977] that Ford’s liberal rule can take exponential time.

The correctness of Ford’s method also follows from a result given in the book Studies in the Economics of Transportation by Beckmann, McGuire, and Winsten [1956]: given a length matrix (l_{i,j}), the distance matrix is the unique matrix (d_{i,j}) satisfying

d_{i,i} = 0 for all i,  (2)
d_{i,k} = min_{j}(l_{i,j} + d_{j,k}) for all i, k with i ≠ k.

Good characterizations for shortest path 1956-1958

It was noticed by Robacker [1956] that shortest paths allow a theorem dual to Menger’s theorem: the minimum length of an P_{0} − P_{n} path in a graph N is equal to the maximum number of pairwise disjoint P_{0} − P_{n} cuts. In Robacker’s words:

the maximum number of mutually disjunct cuts of N is equal to the length of the shortest chain of N from P_{0} to P_{n}.

A related ‘good characterization’ was found by Gallai [1958]: A length function l : A → ℤ on the arcs of a directed graph (V, A) does not give negative-length directed circuits, if and only if there is a function (‘potential’) p : V → ℤ such that l(u, v) ≥ p(v) − p(u) for each arc (u, v).

Case Institute of Technology 1957

The shortest path problem was also investigated by a group of researchers at the Case Institute of Technology in Cleveland, Ohio, in the project Investigation of Model Techniques, performed for the Combat Development Department of the Army Electronic Proving Ground. In their First Annual Report, Leyzorek, Gray, Johnson, Ladew, Meaker, Petry, and Seitz [1957] presented their results.

First, they noted that Shimbel’s method can be speeded up by calculating S^{k} by iteratively raising the current matrix to the square (in the min-sum matrix algebra). This solves the all-pairs shortest path problem in time O(n^{3} log n).

Next, they gave a rudimentary description of a method equivalent to Dijkstra’s method. We quote:

(1) All the links joined to the origin, a, may be given an outward orientation. […]

(2) Pick out the link or links radiating from a, a_{aα}, with the smallest delay. […] Then it is impossible to pass from the origin to any other node in the network by any “shorter” path than a_{aα}. Consequently, the minimal path to the general node α is a_{aα}.

(3) All of the other links joining α may now be directed outward. Since a_{aα} must necessarily be the minimal path to α, there is no advantage to be gained by directing any other links toward α. […]

(4) Once α has been evaluated, it is possible to evaluate immediately all other nodes in the network whose minimal values do not exceed the value of the second-smallest link radiating from the origin. Since the minimal values of these nodes are less than the values of the second-smallest, third-smallest, and all other links radiating directly from the origin, only the smallest link, a_{aα}, can form a part of the minimal path to these nodes. Once a minimal value has been assigned to these nodes, it is possible to orient all other links except the incoming link in an outward direction.

(5) Suppose that all those nodes whose minimal values do not exceed the value of the second-smallest link radiating from the origin have been evaluated. Now it is possible to evaluate the node on which the second-smallest link terminates. At this point, it can be observed that if conflicting directions are assigned to a link, in accordance with the rules which have been given for direction assignment, that link may be ignored. It will not be a part of the minimal path to either of the two nodes it joins. […]

Following these rules, it is now possible to expand from the secondsmallest link as well as the smallest link so long as the value of the third-smallest link radiating from the origin is not exceeded. It is possible to proceed in this way until the entire network has been solved.

(In this quotation we have deleted sentences referring to figures.)

Bellman 1958

After having published several papers on dynamic programming (which is, in some sense, a generalization of shortest path methods), Bellman [1958] eventually focused on the shortest path problem by itself, in a paper in the Quarterly of Applied Mathematics. He described the following ‘functional equation approach’ for the shortest path problem, which is the same as that of Shimbel [1955].

There are N cities, numbered 1, …, N, every two of which are linked by a direct road. A matrix T = (t_{i,j}) is given, where t_{i,j} is time required to travel from i to j (not necessarily symmetric). Find a path between 1 and N which consumes minimum time.

Bellman remarked:

Since there are only a finite number of paths available, the problem reduces to choosing the smallest from a finite set of numbers. This direct, or enumerative, approach is impossible to execute, however, for values of N of the order of magnitude of 20.

He gave a ‘functional equation approach”

The basic method is that of successive approximations. We choose an initial sequence {f_{i}^{(0)}}, and then proceed iteratively, setting

f_{i}^{(k+1)} = Min_{j≠i}(t_{ij} + f_{j}^{(k)}], i = 1, 2, ⋯, N − 1,

f_{N}^{(k+1)} = 0,

for k = 0, 1, 2 ⋯,.

As initial function f_{i}^{(0)} Bellman proposed (upon a suggestion of F. Haight) to take f_{i}^{(0)} = t_{i,N} for all i. Bellman noticed that, for each fixed i, starting with this choice of f_{i}^{(0)} gives that f_{i}^{(k)} is monotonically nonincreasing in k, and stated:

It is clear from the physical interpretation of this iterative scheme that at most (N − 1) iterations are required for the sequence to converge to the solution.

Since each iteration can be done in time O(N^{2}), the algorithm takes time O(N^{3}). As for the complexity, Bellman said:

It is easily seen that the iterative scheme discussed above is a feasible method for either hand or machine computation for values of N of the order of magnitude of 50 or 100.

In a footnote, Bellman mentioned:

Added in proof (December 1957): After this paper was written, the author was informed by Max Woodbury and George Dantzig that the particular iterative scheme discussed in Sec. 5 had been obtained by them from first principles.

Dantzig 1958

The paper of Dantzig [1958] gives an O(n^{2} log n) algorithm for the shortest path problem with nonnegative length function. It consists of choosing in (1) an arc with d(u) + l(u, v) as small as possible. Dantzig assumed

(a) that one can write down without effort for each node the arcs leading to other nodes in increasing order of length and (b) that it is no effort to ignore an arc of the list if it leads to a node that has been reached earlier.

He mentioned that, beside Bellman, Moore, Ford, and himself, also D. Gale and D.R. Fulkerson proposed shortest path methods, ‘in informal conversations’.

Dijkstra 1959

Dijkstra [1959] gave a concise and clean description of ‘Dijkstra’s method’, yielding an O(n^{2})-time implementation. Dijkstra stated:

The solution given above is to be preferred to the solution by L.R. Ford [3 ] as described by C. Berge [4 ], for, irrespective of the number of branches, we need not store the data for all branches simultaneously but only those for the branches in sets I and II, and this number is always less than n. Furthermore, the amount of work to be done seems to be considerably less.

(Dijkstra’s references [3] and [4] are Ford [1956] and Berge [1958].)

Dijkstra’s method is easier to implement (as an O(n^{2}) algorithm) than Dantzig’s, since we do not need to store the information in lists: in order to find a next vertex v minimizing d(v), we can just scan all vertices. Later, using the more efficient data structures of heaps and Fibonacci heaps, one realized that Dijkstra’s method has implementations with running times O(m log n) and O(m+n log n) respectively, where m is the number of arcs (Johnson [1972] and Fredman and Tarjan [1987]).

Moore 1959

At the International Symposium on the Theory of Switching at Harvard University in April 1957, Moore [1959] of Bell Laboratories, presented a paper “The shortest path through a maze”:

The methods given in this paper require no foresight or ingenuity, and hence deserve to be called algorithms. They would be especially suited for use in a machine, either a special-purpose or a generalpurpose digital computer.

The motivation of Moore was the routing of toll telephone traffic. He gave algorithms A, B, C, and D.

First, Moore considered the case of an undirected graph G = (V, E) with no length function, in which a path from vertex A to vertex B should be found with a minimum number of edges. Algorithm A is: first give A label 0. Next do the following for k = 0, 1, …: give label k + 1 to all unlabeled vertices that are adjacent to some vertex labeled k. Stop as soon as vertex B is labeled.

If it were done as a program on a digital computer, the steps given as single steps above would be done serially, with a few operations of the computer for each city of the maze; but, in the case of complicated mazes, the algorithm would still be quite fast compared with trial-and-error methods.

In fact, a direct implementation of the method would yield an algorithm with running time O(m). Algorithms B and C differ from A in a more economical labeling (by fewer bits).

Moore’s algorithm D finds a shortest route for the case where each edge of the graph has a nonnegative length. This method is a refinement of Bellman’s method described above: (i) it extends to the case that not all pairs of vertices have a direct connection; that is, if there is an underlying graph G = (V, E) with length function; (ii) at each iteration only those d_{i,j} are considered for which u_{i} has been decreased at the previous iteration.

The method has running time O(nm). Moore observed that the algorithm is suitable for parallel implementation, yielding a decrease in running time bound to O(nΔ(G)), where Δ(G) is the maximum degree of G. Moore concluded:

The origin of the present methods provides an interesting illustration of the value of basic research on puzzles and games. Although such research is often frowned upon as being frivolous, it seems plausible that these algorithms might eventually lead to savings of very large sums of money by permitting more efficient use of congested transportation or communication systems. The actual problems in communication and transportation are so much complicated by timetables, safety requirements, signal-to-noise ratios, and economic requirements that in the past those seeking to solve them have not seen the basic simplicity of the problem, and have continued to use trial-and-error procedures which do not always give the true shortest path. However, in the case of a simple geometric maze, the absence of these confusing factors permitted algorithms A, B, and C to be obtained, and from them a large number of extensions, elaborations, and modifications are obvious.

The problem was first solved in connection with Claude Shannon’s maze-solving machine. When this machine was used with a maze which had more than one solution, a visitor asked why it had not been built to always find the shortest path. Shannon and I each attempted to find economical methods of doing this by machine. He found several methods suitable for analog computation, and I obtained these algorithms. Months later the applicability of these ideas to practical problems in communication and transportation systems was suggested.

Among the further applications of his method, Moore described the example of finding the fastest connections from one station to another in a given railroad timetable. A similar method was given by Minty [1958].

In May 1958, Hoffman and Pavley [1959] reported, at the Western Joint Computer Conference in Los Angeles, the following computing time for finding the distances between all pairs of vertices by Moore’s algorithm (with nonnegative lengths):

It took approximately three hours to obtain the minimum paths for a network of 265 vertices on an IBM 704.

References

[1956] M. Beckmann, C.B. McGuire, C.B. Winsten, Studies in the Economics of Transportation, Cowles Commission for Research in Economics, Yale University Press, New Haven, Connecticut, 1956.

[1958] R. Bellman, On a routing problem, Quarterly of Applied Mathematics 16 (1958) 87–90.

[1958] C. Berge, Théorie des graphes et ses applications, Dunod, Paris, 1958.

[1976] N.L. Biggs, E.K. Lloyd, R.J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976.

[1958] F. Bock, S. Cameron, Allocation of network traffic demand by instant determination of optimum paths [paper presented at the 13th National (6th Annual) Meeting of the Operations Research Society of America, Boston, Massachusetts, 1958], Operations Research 6 (1958) 633–634.

[1957] G.B. Dantzig, Discrete-variable extremum problems, Operations Research 5 (1957) 266–277.

[1958] G.B. Dantzig, On the Shortest Route through a Network, Report P-1345, The RAND Corporation, Santa Monica, California, [April 12] 1958 [Revised April 29, 1959] [published in Management Science 6 (1960) 187– 190].

[1959] E.W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959) 269–271.

[1970] J. Edmonds, Exponential growth of the simplex method for shortest path problems, manuscript [University of Waterloo, Waterloo, Ontario], 1970.

[1956] L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, Santa Monica, California, [August 14], 1956.

[1987] M.L. Fredman, R.E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the Association for Computing Machinery 34 (1987) 596–615.

[1958] T. Gallai, Maximum-minimum Sätze über Graphen, Acta Mathematica Academiae Scientiarum Hungaricae 9 (1958) 395–434.

[1959] W. Hoffman, R. Pavley, Applications of digital computers to problems in the study of vehicular traffic, in: Proceedings of the Western Joint Computer Conference (Los Angeles, California, 1958), American Institute of Electrical Engineers, New York, 1959, pp. 159–161.

[1955] E. Jacobitti, Automatic alternate routing in the 4A crossbar system, Bell Laboratories Record 33 (1955) 141–145.

[1972] E.L. Johnson, On shortest paths and sorting, in: Proceedings of the ACM Annual Conference 25 (Boston, Massachusetts, 1972), The Association for Computing Machinery, New York, 1972, pp. 510–517.

[1973a] D.B. Johnson, A note on Dijkstra’s shortest path algorithm, Journal of the Association for Computing Machinery 20 (1973) 385–388.

[1973b] D.B. Johnson, Algorithms for Shortest Paths, Ph.D. Thesis [Technical Report CU-CSD-73-169, Department of Computer Science], Cornell University, Ithaca, New York, 1973.

[1977] D.B. Johnson, Efficient algorithms for shortest paths in sparse networks, Journal of the Association for Computing Machinery 24 (1977) 1–13.

[1939] T. Koopmans, Tanker Freight Rates and Tankship Building – An Analysis of Cyclical Fluctuations, Publication Nr 27, Netherlands Economic Institute, De Erven Bohn, Haarlem, 1939.

[1942] Tj.C. Koopmans, Exchange ratios between cargoes on various routes (non-refrigerating dry cargoes), Memorandum for the Combined Shipping Adjustment Board, Washington D.C., 1942, 1–12 [first published in: Scientific Papers of Tjalling C. Koopmans, Springer, Berlin, 1970, pp. 77–86].

[1948] Tj.C. Koopmans, Optimum utilization of the transportation system, in: The Econometric Society Meeting (Washington, D.C., 1947; D.H. Leavens, ed.) [Proceedings of the International Statistical Conferences – Volume V], 1948, pp. 136–146 [reprinted in: Econometrica 17 (Supplement) (1949) 136–146] [reprinted in: Scientific Papers of Tjalling C. Koopmans, Springer, Berlin, 1970, pp. 184–193].

[1959] Tj.C. Koopmans, A note about Kantorovich’s paper, “Mathematical methods of organizing and planning production”, Management Science 6 (1959-60) 363–365.

[1992] Tj.C. Koopmans, [autobiography] in: Nobel Lectures including presentation speeches and laureates’ biographies – Economic Sciences 1969–1980 (A. Lindbeck, ed.), World Scientific, Singapore, 1992, pp. 233–238.

[1947] H.D. Landahl, A matrix calculus for neural nets: II, Bulletin of Mathematical Biophysics 9 (1947) 99–108.

[1946] H.D. Landahl, R. Runge, Outline of a matrix algebra for neural nets, Bulletin of Mathematical Biophysics 8 (1946) 75–81.

[1957] M. Leyzorek, R.S. Gray, A.A. Johnson, W.C. Ladew, S.R. Meaker, Jr, R.M. Petry, R.N. Seitz, Investigation of Model Techniques – First Annual Report – 6 June 1956 – 1 July 1957 – A Study of Model Techniques for Communication Systems, Case Institute of Technology, Cleveland, Ohio, 1957.

[1882] É. Lucas, Récréations mathématiques, deuxième édition, Gauthier-Villars, Paris, 1882–1883.

[1950] R.D. Luce, Connectivity and generalized cliques in sociometric group structure, Psychometrika 15 (1950) 169–190.

[1949] R.D. Luce, A.D. Perry, A method of matrix analysis of group structure, Psychometrika 14 (1949) 95–116.

[1950] A.G. Lunts, Prilozhen ie matrichnoĭ bulevskoĭ algebry k analizu i sintezu releĭno-kontaktiykh skhem [Russian; Application of matrix Boolean algebra to the analysis and synthesis of relay-contact schemes], Doklady Akademii Nauk SSSR (N.S.) 70 (1950) 421–423.

[1952] A.G. Lunts, Algebraicheskie metody analiza i sinteza kontaktiykh skhem [Russian; Algebraic methods of analysis and synthesis of relay contact networks], Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya 16 (1952) 405–426.

[1957] G.J. Minty, A comment on the shortest-route problem, Operations Research 5 (1957) 724.

[1958] G.J. Minty, A variant on the shortest-route problem, Operations Research 6 (1958) 882–883.

[1959] E.F. Moore, The shortest path through a maze, in: Proceedings of an International Symposium on the Theory of Switching, 2–5 April 1957, Part II [The Annals of the Computation Laboratory of Harvard University Volume XXX] (H. Aiken, ed.), Harvard University Press, Cambridge, Massachusetts, 1959, pp. 285–292.

[1955] A. Orden, The transhipment problem, Management Science 2 (1955–56) 276–285.

[1956] J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 January] 1956.

[1956] L. Rosenfeld, Unusual problems and their solutions by digital computer techniques, in: Proceedings of the Western Joint Computer Conference (San Francisco, California, 1956), The American Institute of Electrical Engineers, New York, 1956, pp. 79–82.

[1951] A. Shimbel, Applications of matrix algebra to communication nets, Bulletin of Mathematical Biophysics 13 (1951) 165–178.

[1953] A. Shimbel, Structural parameters of communication networks, Bulletin of Mathematical Biophysics 15 (1953) 501–507.

[1955] A. Shimbel, Structure in communication nets, in: Proceedings of the Symposium on Information Networks (New York, 1954), Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, New York, 1955, pp. 199–203.

[1895] G. Tarry, Le problème des labyrinthes, Nouvelles Annales de Mathématiques (3) 14 (1895) 187–190 [English translation in: N.L. Biggs, E.K. Lloyd, R.J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, pp. 18–20].

[1952] D.L. Trueblood, The effect of travel time and distance on freeway usage, Public Roads 26 (1952) 241–250.

[1873] Chr. Wiener, Ueber eine Aufgabe aus der Geometria situs, Mathematische Annalen 6 (1873) 29–30.

Alexander Schrijver CWI Science Park 123 1098 XG Amsterdam The Netherlands

                   lex.schrijver@cwi.nl

168

Documenta Mathematica · Extra Volume ISMP (2012)