In a non-geostationary satellite constellation with inter satellite links (ISLs), there could be many shortest paths between two satellites in terms of hop count. An efficient routing algorithm Should effectively use these paths in order to distribute traffic to ISLs in a balanced way and to improve the performance of the system. This paper presents and evaluates a novel priority-based adaptive shortest path routing (PAR) scheme in order to achieve this goal. PAR sets the path towards the destination in a distributed manner, using a priority mechanism depending on the past utilization and buffering information of the ISLs. Moreover, to avoid unnecessary splitting of a flow and to achieve better utilization of ISLs, enhanced PAR (ePAR) scheme is proposed. This paper evaluates performance of the proposed techniques by employing an extensive set of simulations. Furthermore, since there are a number of ePAR parameters that should be adjusted depending on the network and traffic characteristics, a detailed analysis of ePAR scheme is provided to form a framework for setting the parameters. This paper also includes a method for adaptation of the proposed algorithms to minimum-delay path routing. Copyright (C) 2006 John Wiley & Sons, Ltd.