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

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.

• 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. Oct 5, 2012 at 19:16
• 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). Oct 5, 2012 at 20:04
• Interesting tidbit, thanks. Will have to look at it. Oct 5, 2012 at 20:05

## 1 Answer

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.
• 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.
– Raphael
Oct 7, 2012 at 22:17