8
$\begingroup$

You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly:

Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each additional edge in the solution, i.e.

$w'(u,v)=a*w(u,v)+1$

This does not work for all values of $a$; $a$ needs to be at least $x$ for this to work. If $a$ is not this minimum number, it might not choose the shortest path. How do I find this minimum value $x$?

Ps. This was done recreationally, I'm done with homework long ago.

$\endgroup$
  • $\begingroup$ If two paths have an equal weight, the one with the fewest edges should be chosen. Sorry. I see that I did not make that clear. $\endgroup$ – The Unfun Cat Oct 5 '12 at 19:16
  • $\begingroup$ You could also do it by adding $\epsilon$ to all edge weights, where $\epsilon < m/e$, m = minimum edge weight, e = number of edges in shortest path (or even overall, if you don't know the shortest path length). $\endgroup$ – BlueRaja - Danny Pflughoeft Oct 5 '12 at 20:04
  • $\begingroup$ Interesting tidbit, thanks. Will have to look at it. $\endgroup$ – The Unfun Cat Oct 5 '12 at 20:05
4
$\begingroup$

Given a graph $G = (V,E,w)$, we define $G'=(V,E,w')$ with $w'(e) = aw(e) + 1$ where $a = |E| + \varepsilon$ for some $\varepsilon \geq 0$ as proposed in the comments of the question.

Lemma
Let $P$ a path in $G$ with cost $C$, i.e. $w(P)=C$. Then, $P$ has cost $aC + |P|$ in $G'$, i.e. $w'(P) = aC + |P|$.

The lemma follows directly from the definition of $w'$.

Call the result of Dijkstra on $G'$ $P$, which is a shortest path in $G'$. Assume $P$ was not a shortest path with fewest edges (among all shortest paths) in $G$. This can happen in one of two ways.

  1. $P$ is not a shortest path in $G$.
    Then, there is a path $P'$ with $w(P') < w(P)$. As $|P|,|P'| \leq |E| \leq a$, this implies that also $w'(P') < w'(P)$ with above lemma¹. This contradicts that $P$ was chosen as shortest path in $G'$.
  2. $P$ is a shortest path but there is a shortest path with fewer edges.
    Then, there is another shortest path $P'$ -- i.e. $w(P) = w(P')$ -- with $|P'| < |P|$. This implies that $w'(P') < w'(P)$ by above lemma, which again contradicts that $P$ is a shortest path in $G'$.

As both cases have led to a contradiction, $P$ is indeed a shortest path with fewest edges in $G$.


That covers one half of the proposition. What about $a < |E|$, i.e. $a = |E| - \varepsilon$ with $\varepsilon \in (0,|E|)$?


  1. Actually, we also need that $a$ or all weights in $G$ are integers. Otherwise, $w(P') < w(P)$ does not cause the weights in $G'$ to be at least $|E|$ apart. This is not a restriction, though; we can always scale $w$ with a constant factor so that all weights are integer, assuming we start with rational weights.
$\endgroup$
  • $\begingroup$ I haven't yet been able to come up with a proof that $a = |E|$ is the smallest $a$ for which this works. I'll give it some more thought. $\endgroup$ – Raphael Oct 7 '12 at 22:17

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.