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!
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.
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|)$.
Dijkstra could have been an option if we were assuming all weights are non-negative.
