(SSSP), and Euler tours. Here, we reproduce the results obtained in [@NeumannW07] (cf. Theorem \[thm:mst\]), in [@BaswanaBDFKN09] (cf. Theorem \[thm:sssp\]), and in [@DoerrJ07] (cf. Theorem \[thm:euler\]), respectively. In doing so, we improve the leading constants of the asymptotic bounds.

Multiplicative Drift Analysis {#sec:drift}
=============================

Drift analysis can be used to track the optimization behavior of a randomized search heuristic over a search space by measuring the progress of the algorithm with respect to a *potential function*. Such a function maps each search point to a non-negative real number, where a potential of zero indicates that the search point is optimal.

\[Additive Drift [@HeY04]\] \[thm:additivedrift\] Let $ S\subseteq\mathbb{R}$ be a finite set of positive numbers and let $\{X^{(t)}\}_{t\in\mathbb{N}}$ be a sequence of random variables over $ S\cup\{0\}$. Let $T$ be the random variable that denotes the first point in time $t\in\mathbb{N}$ for which $X^{(t)}=0$.

Suppose that there exists a constant $\delta>0$ such that $$\label{eq:additivedrift}
{\ensuremath{\operatorname{E}}}\big[X^{(t)}-X^{(t+1)}{\,\big|\,}T>t\big]\ge \delta$$ holds. Then $${\ensuremath{\operatorname{E}}}\big[T{\,\big|\,}X^{(0)}\big] \le \frac{X^{(0)}}{\delta}.$$

This theorem tells us how to link the expected time at which the potential reaches zero to the first time the expected value of the potential reaches zero. If in expectation the potential decreases in each step by $\delta$ then 