A pointer-based algorithm for determining the cycle in the stepping-stone path

When solving a transportation problem by the stepping-stone method, the variables which are to be modified in order to change the basis must be recognized. This requires examining the graph corresponding to these variables plus the variable to enter the basis. Such an investigation can be performed either by scanning the graph or cancelling progressively all rows and columns of the transportation array containing only one basic variable. This paper presents an improvement to the second method and seems to be more efficient than previous approaches. It is shown that the number of operations of the algorithm varies linearly with the sum of the dimensions of the transportation array. A listing of a program in Basic, which uses this algorithm, is given in an annexe to the paper.