Dijkstra privilégie une solution avec le plus petit nombre d'arêtes si plusieurs chemins ont le même poids

Vous pouvez modifier n'importe quel graphe pour que Dijkstra trouve la solution avec le nombre minimal d'arêtes ainsi:$G$

Multipliez chaque poids de bord par un nombre , puis ajoutez au poids pour pénaliser chaque bord supplémentaire dans la solution, c'est-à-dire$a$$1$

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

Cela ne fonctionne pas pour toutes les valeurs de ; doit être au moins pour que cela fonctionne. Si n'est pas ce nombre minimum, il se peut qu'il ne choisisse pas le chemin le plus court. Comment trouver cette valeur minimale ?$a$$a$$x$$a$$x$

Ps. Cela a été fait à titre récréatif, j'ai fini mes devoirs il y a longtemps.

Étant donné un graphique $G = (V,E,w)$, nous définissons $G'=(V,E,w')$ avec $w'(e) = aw(e) + 1$ où $a = |E| + \varepsilon$ pour certains $\varepsilon \geq 0$ comme proposé dans les commentaires de la question.

Lemma
Let$P$ un chemin dans $G$ avec coût $C$, c'est à dire $w(P)=C$. Alors,$P$ a coûté $aC + |P|$ dans $G'$, c'est à dire $w'(P) = aC + |P|$.

Le lemme découle directement de la définition de $w'$.

Appelez le résultat de Dijkstra sur $G'$ $P$, qui est le chemin le plus court $G'$. Présumer$P$ n'était pas un chemin le plus court avec le moins d'arêtes (parmi tous les chemins les plus courts) dans $G$. Cela peut se produire de deux manières.

1. $P$ n'est pas le chemin le plus court $G$.
   Ensuite, il y a un chemin$P'$ avec $w(P') < w(P)$. Comme$|P|,|P'| \leq |E| \leq a$, cela implique que $w'(P') < w'(P)$avec le lemme ci-dessus¹. Cela contredit$P$ a été choisi comme chemin le plus court $G'$.
2. $P$est un chemin le plus court mais il y a un chemin le plus court avec moins d'arêtes.
   Ensuite, il y a un autre chemin le plus court$P'$ -- c'est à dire $w(P) = w(P')$ -- avec $|P'| < |P|$. Cela implique que$w'(P') < w'(P)$ par ci-dessus lemme, ce qui contredit à nouveau que $P$ est le chemin le plus court $G'$.

Comme les deux cas ont conduit à une contradiction, $P$ est en effet le chemin le plus court avec le moins d'arêtes $G$.

Cela couvre la moitié de la proposition. Qu'en est-il de$a < |E|$, c'est à dire $a = |E| - \varepsilon$ avec $\varepsilon \in (0,|E|)$?

1. En fait, nous avons également besoin de cela $a$ ou tous les poids $G$sont des entiers. Autrement,$w(P') < w(P)$ ne cause pas les poids $G'$ être au moins $|E|$une part. Ce n'est cependant pas une restriction; nous pouvons toujours évoluer$w$ avec un facteur constant afin que tous les poids soient entiers, en supposant que nous commençons par des poids rationnels.