Dijkstra bevorzugt eine Lösung mit der geringsten Anzahl von Kanten, wenn mehrere Pfade das gleiche Gewicht haben

Sie können jeden Graphen so ändern , dass Dijkstra die Lösung mit der minimalen Anzahl von Kanten findet: $G$

Multiplizieren Sie jedes Kantengewicht mit einer Zahl und addieren Sie dann zum Gewicht, um jede zusätzliche Kante in der Lösung zu bestrafen, d. H. $a$ $1$

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

Dies funktioniert nicht für alle Werte von $a$ ; $a$ muss mindestens $x$ damit dies funktioniert. Wenn $a$ nicht diese Mindestanzahl ist, wählt es möglicherweise nicht den kürzesten Pfad. Wie finde ich diesen Mindestwert $x$ ?

Ps. Dies wurde in der Freizeit gemacht, ich bin mit den Hausaufgaben vor langer Zeit fertig.

algorithms graph-theory shortest-path Die Unfun Cat
quelle

Wenn zwei Pfade das gleiche Gewicht haben, sollte der mit den wenigsten Kanten ausgewählt werden. Es tut uns leid. Ich sehe, dass ich das nicht klar gemacht habe.

Die Unfun Cat

Man könnte es auch tun , durch Zugabe an alle Kantengewichte, wo , = m Mindestkantengewicht, e = Anzahl der Kanten in kürzestem Weg (oder sogar insgesamt, wenn Sie nicht den kürzesten Weg wissen Länge) .

ϵ

$\epsilon$

ϵ < m / e

$\epsilon < m/e$

BlueRaja - Danny Pflughoeft

Interessanter Leckerbissen, danke. Muss es mir ansehen.

Die Unfun Cat

Antworten:

Wenn ein Graph , definieren wir mit wobei für einige wie in den Kommentaren der Frage vorgeschlagen. $G = (V,E,w)$ $G'=(V,E,w')$ $w'(e) = aw(e) + 1$ $a = |E| + \varepsilon$ $\varepsilon \geq 0$

Lemma
Sei ein Pfad in mit Kosten , dh . Dann hat gekostet in ist dh. $P$ $G$ $C$ $w(P)=C$ $P$ $aC + |P|$ $G'$ $w'(P) = aC + |P|$

Das Lemma folgt direkt aus der Definition von . $w'$

Nennen Sie das Ergebnis von Dijkstra auf , dem kürzesten Weg in . Es sei angenommen mit dem wenigstenen Kanten nicht ein kürzester Weg war (unter allen kürzesten Pfaden) in . Dies kann auf zwei Arten geschehen. $G'$ $P$ $G'$ $P$ $G$

$P$ ist kein kürzester Weg in . Dann gibt es einen Pfad mit . As , dies impliziert, dass auch mit dem obigen Lemma¹ ist. Dies widerspricht, dass als kürzester Weg in . $G$
$P'$ $w(P') < w(P)$ $|P|,|P'| \leq |E| \leq a$ $w'(P') < w'(P)$ $P$ $G'$
$P$ ist ein kürzester Weg, aber es gibt einen kürzesten Weg mit weniger Kanten.
Dann gibt es einen anderen kürzesten Weg - dh - mit. Dies impliziert, dass durch das obige Lemma ist, was wiederum widerspricht, dass ein kürzester Weg in . $P'$ $w(P) = w(P')$ $|P'| < |P|$ $w'(P') < w'(P)$ $P$ $G'$

Da beiden Fälle zu einem Widerspruch geführt haben, ist in der Tat ein kürzester Weg mit dem wenigstenen Kanten in . $P$ $G$

Das deckt die Hälfte des Satzes ab. Was ist mitdh mit ? $a < |E|$ $a = |E| - \varepsilon$ $\varepsilon \in (0,|E|)$

Eigentlich brauchen wir auch, dass oder alle Gewichte in ganze Zahlen sind. Andernfalls bewirkt nicht, dass die Gewichte in mindestensein Teil. Dies ist jedoch keine Einschränkung. Wir können immer mit einem konstanten Faktor skalieren , so dass alle Gewichte ganzzahlig sind, vorausgesetzt, wir beginnen mit rationalen Gewichten. $a$ $G$ $w(P') < w(P)$ $G'$ $|E|$ $w$

Raphael
quelle

Ich konnte noch keinen Beweis dafür finden, dassist das kleinste für das dies funktioniert. Ich werde noch etwas darüber nachdenken.

a = | E |

$a = |E|$

a

$a$

Raphael