A 'STRING ALGORITHM' FOR SHORTEST PATHS IN DIRECTED NETWORKS

摘要

It consists of making an inelastic string model of the network, with knots corresponding to nodes and string-lengths proportional to the corresponding distances, and then stretching the knots P and Q as far apart t-s is possible without breaking the string;this produces at least one straight path from P to Q, and each such straight path corresponds to a shortest path in the network.