An Algorithm for a Dynamic Programming Model of Fractional Flows

In an earlier paper, the author introduced an n-dimensional dynamic programming model of fractional flows, characterized its solutions under general conditions, and developed methods for their computation. The latter, which resemble algorithms for n-state Markovian decision processes, break down when the costs are undiscounted and the flow matrices are nontransient. Here, an algorithm is presented that computes many of the quantities of interest more efficiently under milder assumptions. In addition, some of our earlier results for the undiscounted case are extended to models with nontransient flow matrices.