Lexicographic perturbation for euclidean shortest path instances?
I think you're unlikely to get a good answer, because this is tied up in difficult and unsolved algebraic problems. The issue is that Euclidean path lengths (for points with integer coordinates) can be expressed as sums of square roots, but we don't know how small the difference between two distinct sums of square roots can be. Because of this, we also don't know how far apart the shortest path length and second-shortest distinct path length between a given pair of vertices can be, and therefore we don't know how small we have to make a perturbation to prevent it from changing the shortest path to a path that wasn't originally shortest.

For the same reason, shortest paths in Euclidean graphs are not really known to be solvable in polynomial time, in models of computation that take into account the bit complexity of the inputs, even though Dijkstra is polynomial in a model of computation allowing constant-time real-number arithmetic. So asking for a polynomial time algorithm for a more complicated variant of the problem in which the bit complexity is unavoidable seems likely to have a negative answer.