Using Dijkstra to find shortest path in relation to two weight functions?
Let $\epsilon&gt;0$ be an infinitesimal. Define a new weight function $w(v) = w_2(v) + \epsilon w_1(v)$, and run Dijkstra with respect to this weight function.

How do you implement infinitesimals? There are two options. The first is to let $\epsilon$ be a small enough number. For example, if $W_1$ is the maximal $w_1$-weight and there are $n$ nodes, then $\epsilon &lt; 1/(nW_1)$ should be small enough (why?). The other option is to notice that you only have to be able to compare numbers of the form $w_2 + \epsilon w_1$. We have $x_2 + \epsilon x_1 \leq y_2 + \epsilon y_1$ if either $x_2 &lt; y_2$ or $x_2 = y_2$ and $x_1 \leq y_1$. Using this comparison oracle, you can implement infinitesimals in earnest.