Likely I have misunderstood your idea, but under one interpretation, I do not think it can work, for the following reason. Consider an example like this: <br /> ![shortest][1] <br /> The view from $s$ only shows edges surrounding the weight-10 region, and from that point of view, your algorithm would select to cross the weight-9 region (if I understand it correctly). However, that weight-11 region is "hiding" a low-weight region, which would be much more economical to traverse. It does not seem to me one can determine "the sequence of polygons through which the shortest path will pass" only by looking at the weights to either side region-separating edges. My sense is that determining the sequence of polygons the shortest path crosses is about as difficult as finding the true shortest path. [1]: http://cs.smith.edu/~orourke/MathOverflow/ShortestWeighted.jpg