The recent increase in HyperText Transfer Protocol (HTTP) traffic on the World Wide Web (WWW) has generated an enormous amount of log records on Web server databases. Applying a Web mining technique on these server log records can discover any potentially useful patterns and reveal user access behaviors on the Web site. In this paper, we propose a new approach for mining user access patterns for predicting Web page requests. Our approach consists of two major steps. First, the shortest path algorithm in graph theory is applied to find the distances between the Web pages. In order to capture user access behavior on the Web, the distances are derived based on user traversal paths, as opposed to static structural hyperlinks. We refer to these distances as Minimum Reaching Distance (MRD) information. In the second step, the association rule mining technique is applied to form a set of predictive rules. In order to increase the accuracy and reduce the space complexity, the MRD information is used to prune the results from the association rule mining. Experimental results from a real Web data set show that our approach improved the performance over the existing Markov model approach in terms of the precision and recall, and the reduction of user browsing time on the Web.