1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ If w2 is tie breaker then this is easy, find all shortest paths with relation to w1 and do a tie breaker with w2. $\endgroup$ – Bartosz Przybylski Apr 19 '14 at 18:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Gilad May 28 '18 at 2:39
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.