Dijkstra to favor solution with smallest number of edges if several paths have same weight

Problem Detail: 

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.

Asked By : The Unfun Cat

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4887