Probability Distribution Of Random Network Shortest Path

This paper investigates the shortest path problem of stochastic networks, and develops a new algorithm based on Markov skeleton processes to obtain the distribution function of the shortest path. As one of classical issues in stochastic network analysis, the shortest path problem has motivated many researchers to develop methods to compute the distribution of the length of shortest path. But these methods have put restrictions on the distribution functions of the arc length (for example, assume that the arc lengths are continuously or exponentially distributed random variables). When the distribution functions of arc length don't satisfy those restrictions, the methods are no longer applicable, and we must do some research into the case that the arc lengths are generally distributed. This paper uses the theory of Markov skeleton processes to compute the distribution of the length of the shortest path in a stochastic network with generally distributed arc lengths. A Markov skeleton process is constructed from the original network, and the time until the Markov skeleton process gets absorbed in the absorbing state from the initial state is just equal to the length of the shortest path in the original network. Moreover, the backward equations can be applied to obtain the distribution of the length of the shortest path. Chapter 1 introduces the developmental history and present condition of the shortest problem. Chapter 2 introduces the Markov skeleton process (MSP), and presents its definition and some basic properties. Chapter 3 constructs the Markov skeleton process, and presents the state space of the MSP. Chapter 4 presents the algorithm to calculate the distribution of the length of the shortest path. In Chapter 5, the method is illustrated through solving two examples.