On Finding the Paths Through a Network

Informally, a directed graph consists of a set of vertices or nodes together with a set of directed edges joining the nodes. (All of the figures below show directed graphs; for a formal definition see page 10 of Ref. 1. There may be more than one edge with the same originating and terminating nodes, and the originating and terminating nodes of an edge may coincide.) Common examples of directed graphs are state diagrams of systems: the nodes represent states of the system and an edge directed from node Ni to node N t means that it is possible for the system to go directly from state N, to state N, . The following questions concerning the paths through a directed graph arose in testing for possible errors sections of the stored program of a No. 1 ESS electronic switching system."' However, these questions and the algorithms for their solution seem of sufficient general interest to warrant stating them independently of their origin. Given a directed graph G, the questions are: (i) Find the set a of all paths through G with prescribed originating and terminating nodes. (A path is just what one would expect; a formal definition is given in Section II.) (ii) Find a small subset of a which contains every edge occurring in a. (iii) Find a small subset of a which contains all the edge-edge transitions occurring in any path in a. (iv) If a probability measure is associated with the edges of G, find the most probable paths in a. These questions and algorithms for their solution are discussed in Sections III, V, VI, and VII, respectively.