Bei Djkstra mit negativen Kantengewichten positive Konstante addieren?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

Studium, Schule, Mathematik, Mathe, rechnen, gewichte, Informatik, Theoretische Informatik, Uni, Algorithmus, Graphentheorie, Kante
Unterschenkel nicht mehr richtig beweglich. Kann ich ihn dafür trainieren?

Hallo, vor 4 Jahren hatte ich einen Fahrrad-Unfall, bei dem ich mir meinen Unterschenkel gebrochen war (Unterschenkel-Fraktur hieß es). Der Bruch war so kompliziert, dass ich erst ein viertel Jahr später wieder richtig laufen konnte (ohne Krücken usw). Ich habe dennoch schon nach den ersten Tagen einige Einschränkungen gemerkt. Dazu gehörten, dass ich meinen linken Fuß nicht so sehr anheben konnte, wie meinen rechten, außerdem konnte ich mein Gleichgewicht weniger halten, als es bei meinem rechten Bein war. Das hat mich zuerst nicht gestört, bis heute. Ich muss einen Tanz lernen, welcher zuerst simple erscheint, aber sobald ich mein Gewicht auf mein linkes Bein verlagere, kann ich es schwerer bewegen, als wenn ich mein Gewicht auf das andere Bein verlagere, denn bei diesem Tanz steht man auf dem vorderen Teil der Fußfläche, wenn das jeweilige Bein belastet wird. Gibt es eine Möglichkeit dies zu trainieren, muss ich einfach nur weiter den Tanz üben oder muss wäre es besser, wenn ich den Tanz nicht lerne? Bei meinem anderen Bein, schaff ich den Schritt, doch sobald die Schritte schneller werden, hört mein linkes Bein quasi von selbst auf, obwohl es sich noch bewegen muss. Ich werde den Tanz verlinken, damit man sich eventuell besser vorstellen kann, wie die Gewichtsverlagerung der Schritte ist

Der Link zum Video: https://www.youtube.com/watch?v=47jVdOrTj5s

Muskeln, tanzen, dehnen, Training, Gleichgewicht, Gesundheit und Medizin, gewichte, Sport und Fitness, Unterschenkel

Meistgelesene Fragen zum Thema Gewichte