# Using Dijkstra to find shortest path in relation to two weight functions?

I'm given a graph and two weight functions, $w_1$ and $w_2$, such that there doesn't exist a negative loop in the graph in $w_1$ and $w_2$. I'm also given two vertices, $s$ and $t$, and am asked to find the lightest path from $s$ to $t$ in relation to $w_1$, out of all the lightest paths from $s$ to $t$ in relation to $w_2$.

I get that this question begs for me to modify Dijkstra somehow, but I just can't seem to find the intuition to do so. Any guidance would be appreciated!

• If w2 is tie breaker then this is easy, find all shortest paths with relation to w1 and do a tie breaker with w2. Apr 19, 2014 at 18:08
• cs.stackexchange.com/q/24768/755
– D.W.
Mar 23, 2023 at 18:50

Let $\epsilon>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 < 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 < y_2$ or $x_2 = y_2$ and $x_1 \leq y_1$. Using this comparison oracle, you can implement infinitesimals in earnest.
• The first option does not work, e.g. a graph with two vertices and two edges and $w_1(e_1) = 0, w_1(e_2) = 1, w_2(e_1) = 1.1, w_2(e_2) = 1$ May 28, 2018 at 2:39
Let $G$ be the relevant graph. Run $\text{Bellman-Ford}(G, s, w_2)$ and for every $v ∈ V$: $d(v)=δ(s,v)$. Now for every $(u,v) ∈ E$, if $d(v)≠d(u)+w_2(u,v)$ erase ($u$,$v$) from $G$. You are left with $G'$, the graph with all lightest paths from $s$ according to $w_2$. Run $\text{Bellman-Ford}(G', s, w_1)$ to find the lightest path from $s$ to $t$ in relation to $w_1$, out of all the lightest paths from $s$ to $t$ in relation to $w_2$.
It is done by $O(|E||V|)$.