# Lexicographic perturbation for euclidean shortest path instances?

Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such that the following statements hold:

1. For every pair $s\neq t \in V$, there is a unique shortest s-t-path $P_{s,t}$ in $G$ w.r.t. the euclidean weight function $c(v,w)=|\pi'(v)-\pi'(w)|_2$.

2. $P_{s,t}$ is also a shortest s-t-path w.r.t. the original vertex positions $\pi$.

3. $\pi'$ can be deterministically computed in polynomial time given $\pi$. The length of the numbers occuring in $\pi'$ are polynomially bounded in the length of those in $\pi$.

I know that lexicographic perturbation is a standard procedure to do this deterministically. Sadly there is no simple way to modify the distance of only a single edge in euclidean instances.

Is there any known approach that can be applied to those euclidean instances? Even a randomized perturbation algorithm would be interesting for me.