Shortest paths perturbation
Probably the simplest approach is to perturb the edge weights symbolically rather than numerically.  Intuitively, you'd like to reassign the weight of each edge as
$$
\tilde{w}(e) = w(e) + \varepsilon \cdot w'(e)
$$
where $w(e)$ is the original edge weight, $w'(e)$ is a secondary edge weight, and $\varepsilon$ is a global scaling factor.  This perturbation scheme has to satisfy two requirements:


Every shortest path with respect to the perturbed edge weights must be also a shortest path with respect to the original edge weights.  It's not hard to prove that for any function $w'$, this property holds for all sufficiently small scaling factors $\varepsilon$.  Rather than spending time figuring out how small "sufficiently small" is, consider instead the limiting behavior as $\varepsilon$ approaches $0$.  Then your perturbed edge weights are best formalized as two-dimensional vectors
$$
\tilde{w}(e) = \big( w(e), w'(e) \big).
$$
The length of any path is also a vector, obtained by summing the vector-weights of each edge on the path.  Comparisons between length vectors are performed lexicographically:
$$
(a, a') &lt; (b, b') \iff a&lt;b \text{ or } (a = b \text{ and } a'&lt;b')
$$
This definition trivially implies that for any paths $\alpha$ and $\beta$, if $w(\alpha) &lt; w(\beta)$, then $\tilde{w}(\alpha) &lt; \tilde{w}(\beta)$.  One nice feature of this scheme is that if shortest paths with respect to $w$ are already unique, the algorithm never even notices $w'$.
Shortest paths with respect to the perturbed edge weights must be unique.  It suffices to choose a function $w'$ such that shortest paths with respect to $w'$ are unique.  There are two standard methods for finding such a function $w'$.


The simplest method is to generate each $w'(e)$ randomly.  The Isolation Lemma of Mulmuley, Vazirani, and Vazirani implies that if each $w'(e)$ is chosen independently and uniformly at random from the set $\{1, 2, \dots, n^4\}$, then with probability $1-O(1/n)$, all shortest paths are unique.  This scheme works for any shortest path algorithm with no run-time penalty and little modification to the algorithm, but it does have a small probability of failure.
A more complex deterministic method (which linear-programming people know as "lexicographic perturbation") indexes the edges from $1$ to $m$ and defines $w'(e_i) = 2^i$.  Clearly every subset of edges has distinct total $w'$eight.  However, using this method requires manipulating $m$-bit integers, so it's more efficient to implement this method symbolically as well.  For any paths $\alpha$ and $\beta$, we have $w'(\alpha) &lt; w'(\beta)$ if and only if the minimum edge-index in $\alpha\setminus\beta$ is smaller than the minimum edge-index in $\beta\setminus\alpha$.  Most shortest-path algorithms only compare paths that share a common prefix (starting at some source node $s$) and are otherwise edge-disjoint.  With an appropriate dynamic tree data structure (e.g., link-cut trees or top trees), it is possible to find the node where the two paths split and the minimum edge-index along the disjoint suffixes in $O(\log n)$ amortized time.  So, this scheme is always correct, but it imposes a penalty in the running time that is only $O(\log n)$ if your algorithm has the right structure, and it requires significant data structure overhead.



You can guess which method I recommend.  My recent journal paper with Sergio Cabello and Erin Chambers describes both of these perturbation schemes in more detail.

There are also more specialized methods for specific algorithms and specific classes of graphs.


  I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible?


I don't know.  In particular, the randomized perturbation scheme I described does not have this property.