Shortest Paths in Probabilistic Graphs

Abstract

This paper considers the problem of finding shortest-path probability distributions in graphs whose branches are weighted with random lengths, examines the consequences of various assumptions concerning the nature of the available statistical information, and gives an exact method for computing the probability distribution, as well as methods based on hypothesis testing and statistical estimation. It presents Monte Carlo results and, based on these results, it develops an efficient method of hypothesis testing. Finally, it discusses briefly the pairwise comparison of paths.