Article ID: | iaor20014156 |
Country: | United States |
Volume: | 27 |
Issue: | 2 |
Start Page Number: | 133 |
End Page Number: | 143 |
Publication Date: | Mar 1996 |
Journal: | Networks |
Authors: | Tsitsiklis John N., Polychronopoulos George H. |
Keywords: | programming: dynamic |
We consider shortest path problems defined on graphs with random arc costs. We assume that information on arc cost values is accumulated as the graph is being traversed. The objective is to devise a policy that leads from an origin to a destination node with minimal expected cost. We provide dynamic programming algorithms, estimates for their complexity, negative complexity results, and analysis of some possible heuristic algorithms.