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, rechnen, gewichte, Informatik, Theoretische Informatik, Universität, Algorithmus, Graphentheorie, Kante
Wisst ihr, was man dagegen noch tun kann?

Guten Tag,

also es geht bei mir um ein sehr großes Problem und ich würde gerne wenige Ratschläge oder Meinungen dazu hören.. Das wäre sehr freundlich. Und bitte keine Scherze.

Ich möchte vorerst sagen, dass ich keine faule Schülerin bin. Ich habe in Deutsch und Englisch eine 1 und auch die anderen Fächer passen alle, bis auf Mathe.

Dieses Jahr hatte ich eine wirkliche "Hexe" in Mathe.. Nun habe ich eine 5. Letztes Jahr eine 2. Ich habe nur schlechte Noten bei ihr geschrieben und ich hatte sehr viel Stress mit ihr, obwohl ich mich immer mit Lehrern verstehe. Nun ist es so, dass ich in der Abschlussprüfung, wie ein Freund von mir, eine 4 geschrieben habe. Er war schlechter in Mathe, hat schlimmere Noten geschrieben und er hat nun eine 4 auf dem Zeugnis und ich immer noch eine 5.. Also ist Mathe irgendwie daran schuld, dass ich nicht auf das Gymnasium komme.

Ich bin also am überlegen, ob ich ein Brief (mitsamt einer neuen Bewerbung) an die Schule schicke und davon berichte, dass das Sachverhalten an dieser Schule einfach nicht gut ist, weil es so oft schon vorgekommen ist, dass andere Schüler bevorzugt werden.

Ich möchte unbedingt auf dieses Gymnasium, aber ich habe das Gefühl, dass sie mir das einfach versauen wollte..

Es wäre extrem nett, wenn ihr vielleicht Ratschläge hättet.. Wirklich, ich bin im Moment etwas fertig deswegen.

Schule, Mathematik, Abschluss, Gymnasium, Lehrer, Zeugnis, ungerecht-behandelt, Ausbildung und Studium

Meistgelesene Beiträge zum Thema Mathematik