Optical Burst Switching (OBS) aims to provide higher utilization and greater flexibility at a lower cost and reduced complexity than current optical circuit switched networks. We introduce a new routing protocol for Optical Burst Switching, Shortest Path Prioritized Random Deflection Routing (SP-PRDR), that aims to lower burst loss probabilities while only using limited state information from traditional Internet Protocol technologies. We show, through analysis and simulation, that loss in OBS networks is significantly reduced by SP-PRDR for loads that previously gave moderate or low losses in the unmodified case. In the simulation examples studied, by using SP-PRDR we are able to increase the input load by approximately 15-20% while maintaining a constant burst loss probability of 10-3. Additionally, unlike other schemes, we show that the worst case burst loss probability of SP-PRDR is provably upper-bounded by the burst loss probability of standard OBS.