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
2 Antworten
-9 + 10 ist übrigens +1. -8+10 ist +2.
Du hast hinterher also nur noch positive Kantengewichte.
Ja, aber Djkstra versagt ja schon bei negativen Kantengewicht generell. Das heißt, man muss zuerst ein Beispiel finden, bei denen Djkstra mit negativen Kantengewichten ausnahmsweise funktioniert und dann zeigen, dass bei bei Addieren von der konstanten |k| versagt.
Das sehe ich da in der Aufgabenstellung so nicht. Es geht generell darum, ob man mit der Strategie "Aufaddieren" das Problem mit den negativen Kantengewichten lösen kann. Das wäre dann nämlich eine einfache Idee, um Dijkstra abzuwandeln...
Nimm mal C_4, also den Kreisgraphen mit 4 Knoten.
Drei der Kanten haben das Gewicht -1, eine Kante hat das Gewicht -2, die Knoten an der letzten Kante seien u und v.
In diesem Graphen ist der kürzeste Weg zwischen u und v gerade der Weg "außenrum", der hat das Gesamtgewicht -3, der andere "direkte" Weg hat das Gewicht -2.
Addiere ich jetzt einfach 2 auf alle Gewichte, so findet Dijkstra den "direkten" Weg mit dem Gewicht 0, weil der andere ja das Gewicht 3 hat und daher länger ist.
Ich kann also das Ergebnis mit den erhöhten Gewichten nicht auf den ursprünglichen Graphen übertragen und scheitere mit dieser Strategie.
Ob auf dem ursprünglichen Graphen Dijkstra scheitert, ist ja gar nicht die Frage. Letztlich läuft es auf das folgende heraus: Kann ich auf eine simple Art und Weise Dijkstra so abwandeln, dass negative Gewichte kein Problem sind?
Danke für die Antwort. Ich habe mir jetzt einen Graph überlegt mit 6 Knoten überlegt und erstmal mit negativen Kanten den kürzesten Weg bestimmt. Dadurch dass die Kanten ja alle negativ sind und ich bei djkstra die Wege addiere, werden die Kanten ja ziemlich schnell klein. Die Kanten in meinem Beispiegraph haben die Beschriftung -9, -6, -5, -4, -3, -2 und -1 Wenn ich z.b. einen Kante habe die mit -9 beschriftet ist und ich danach eine Kante in den Graphen mitreinnehme, die -5 hat, bin ich schon bei -14. Dann nehme ich eine Kante mit rein, die -3 hat. Da bin ich bei -17 usw. Dann brauch ich doch ur noch die -17er Kante entlang zu laufen und die kleinsten negativen Zahlen die ich finde reinnehme. Ende hatte ich ein Kantengewicht von -32.
Dann hab ich sämtliche Kante + 9 addiert und hatte einen völlig anderen Baum der kürzesten Wege.
Hab ich somit die aufgabe gelöst?
Oder ist das völlig am Thema vorbei?
Ich müsste jetzt den Graphen sehen. Es geht ja darum, dass du mit dem Dijkstra-Algorithmus auf dem Graphen mit den erhöhten Kantengewichten Lösungen findest, die auf dem Graphen mit dem niedrigen Kantengewichten nicht unbedingt Lösungen sind. Es geht nicht darum, welche Wege Dijkstra auf dem ursprünglichen Graphen findet, sondern nach meinem Verständnis nur darum, dass man mit Dijkstra auf dem neuen Graphen kein Optimum für den alten Graphen findet.
Hattest du mein Beispiel nachvollzogen?
Danke. ja das Beispiel hab ich nachvollziehen können.Ich habe jetzt diesen Graphen genommen und habe als Startknoten v3 festgelegt
https://www.directupload.net/file/d/5864/y4ic7sdu_png.htm
Dann würde ich von v3 mit -9 nach v2 kommen. Über v2 komme ich mit -5 nach v0. Das sind -9 + -5 = -14. Mit -14 komm ich über -3 nach v1. Das wäre -17. Mit v1 über -5 nach v5. Das wären -22. Mit v5 über die Kante -6 nach v4. Das wären -28. Dann würde der Baum der kürzesten Wege so aussehen wie hier markiert.
Jetzt die Frage. Kann ich das wirklich so machen? Weil spätestens ab dem Zeitpunkt, wo ich -14 für v0 hatte, führe ich ja eigentlich keine wirkliche Suche durch, sondern lauf nur noch die kürzesten Wege vom Knoten aus ab.
Wenn ich jetzt sämtliche Wege +9 mache, kommt ein ganz andere Baum der kürzesten Wege raus https://www.directupload.net/file/d/5864/kplk22uv_png.htm
Und nochmal: Über das Verfahren von Dijkstra auf dem Graphen mit den negativen Gewichten ist in der Aufgabe GAR nichts gefragt. Warum willst du das unbedingt machen? Und ob der Baum ein anderer ist, ist auch nicht entscheidend, es kann ja auch zwei Bäume kürzester Wege geben, die komplett anders sind, das wäre kein Problem. Du musst nur zeigen, dass du mit dem "veränderten" Dijkstra-Verfahren nicht unbedingt eine optimale Lösung findest.
Wenn ich mir das erste Bild anschaue, sehe ich auf Anhieb, dass das ja keine kürzesten Wege sind - was kein Wunder ist, weil Dijkstra ja auch nicht funktionieren muss bei negativen Gewichten.
Der Weg v0 v2 v3 v5 v4 wäre ja ein kürzer v0-v4-Weg als der im Baum ermittelte.
Ok, langsam versteh ich den Fehler. Ich hab die ganze Zeit auf dem Baum mit dem negativen Kanten gearbeitet. Dort djkstra laufen lassen. Dann den Baum mit den veränderten Kanten erstellt und darüber djkstra laufen gelassen und die Ergebnisse verglichen.
Wenn ich jetzt aber, was du wohl meinst, nur den veränderten Baum betrachtet und dort Djkstra laufe, dann könnte ich ja gleich mir einen Graphen mit negativen Gewichten überlegen. Das wäre dann der transformierte Graph..dann zeigen, dass er nicht funktioniert und dann halt | k| abziehen, damit ich für die aufgabenstellung den ursprünglichen graphen habe..
Genau, auf dem transformierten Graphen funktioniert Dijkstra. Aber die Lösungen auf dem transformierten Graphen lassen sich aber nicht auf den ursprünglichen Graphen übertragen - ein auf dem transformierten Graph kürzester Weg ist (nach Abzug von |k|) eben nicht unbedingt ein kürzester Weg auf dem ursprünglichen Graphen.
Wenn alle Gewichte negativ sind und ich den Betrag der kleinsten Zahl | k| auf alle Gewichte addiere, sind alle Zahlen positiv. Ich müsste also ein Beispiel finden wo Djkstra mit positiven Gewichten den kürzesten Weg nicht findet?
Auf dem transformierten Graphen findet Dijkstra natürlich den kürzesten Weg bezogen auf die transformierten Gewichte. Aber wenn du diesen Weg dann mit den alten Gewichten betrachtest, dann ist er u. U. nicht mehr der kürzeste. Darum geht es.
Ja, aber das ist doch dann das, was ich in den 2 Bildern gemacht habe?
Hier das wo es nicht klappt: https://www.directupload.net/file/d/5864/y4ic7sdu_png.htm
Und da dort die kleinste Zahl = -9 war, alles mit | k | = 9 transformiert:
https://www.directupload.net/file/d/5864/kplk22uv_png.htm
Auf dem zweiten Bild findet man jetzt die kürzesten Wege. Wenn ich den Graph mit dem Gewicht aus den ersten Bild betrachte (den negativen) findet man diese Wege natürlich nicht (sondern andere).
Das es andere sind, ist nicht das Thema, sondern dass sie nicht kürzeste sind. Es kann ja mehrere kürzeste Wege geben. Bisher zeigst du nur, dass unterschiedliche Lösungen herauskommen, das wäre aber erstmal kein Problem.
Du müsstest jetzt noch einen Weg benennen, der im transformierten gefunden wird, im ursprünglichen aber nicht kürzester ist. Dann bist du in der Tat fertig. Insgesamt finde ich dein Beispiel aber immer noch sehr aufwändig, da kann man auch ein sehr viel einfacheres finden, bei dem man das dann auch gleich sieht.
Aber das ist doch das was ich in rot markiert gemacht habe, oder?
Im transformierten Graph starte ich in v3. Gehe dann über die mit 0 beschriftete Kante zu v2. Von v2 geh ich über die mit 4 beschriftete Kante zu v0. Dann ziehe ich mich wieder zurück zu v3. Von v3 findet man über die mit 4 beschriftete Kante v5 und über die mit 5 beschriftete Kante v4. Jetzt sind alle Kanten von Djkstra entdeckt, nur noch v1 fehlt. Der kürzeste Weg wäre von v2 zu v1 über die Kante mit Gewicht 7. Damit sind jetzt alle Knoten entdeckt und ich habe den Baum der kürzesten Wege. Rot markiert.
Im ersten Bild ist ist der Baum der kürzesten Wege jedoch ein anderer. Das heißt mein rot markierter Weg im 2. Bild wäre im 1. Bild ein längerer Weg.
Oder kann man den Baum der kürzesten Wege nicht als Weg bezeichnen? Kann man damit nur klassische Wege bezeichnen, von Kanten zu Kante.
Dann könnte ich ja sagen. Im transfomrierten graph ist der kürzeste Weg von v3 nach v5 der Weg (v3, v5) mit der Länge 4. Im ursprünglichen Graph ist (v3,v5) aber nicht der kürzeste um von v3 nach v5 zu gelangen, sondern stattdessen (v3, v2, v0, v1, v5).
Geht das?
Ein Baum ist kein Weg, richtig, du musst also einen Weg bezeichnen. Und das hast du ja am Ende auch getan, genau darauf wollte ich heraus.
Noch mal die Argumentation zusammengefasst:
Man hat einen Graph mit ausschließlich negativen Gewichten. Jetzt weiß man bereits, dass Dijkstra darauf nicht unbedingt die kürzesten Wege findet. Um die negativen Gewichte loszuwerden, hebt man alle Gewichte durch Addition eines konstanten Werts so an, dass sie gerade alle nicht mehr negativ sind. Auf dem so transformierten Graphen berechnet man mit Dijkstra die kürzesten Wege, weil hier Dijkstra ja funktioniert. Sind das auch alles kürzeste Wege auf dem ursprünglichen Graph mit den ursrprünglichen Gewichten?
NEIN. Denn auf dem transformierten Graphen erhält man mit Dijkstra u. a. als kürzesten Weg zwischen v3 und v4 den Weg v3-v4 mit Länge 4. Auf dem ursprünglichen Graphen hat dieser Weg die Länge -5. Der Weg v3-v2-v0-v1-v5 aber hat hier die Länge -22, ist also "kürzer".
Mit der Strategie "addiere einfach einen konstanten Wert" kann man als Dijkstra also nicht zu einem funktionierenden Algorithmus für Graphen mit negativen Gewichten umbauen.
Danke dir für die Hilfe
Schwere Geburt bei mir ^^ Aber danke für dein Durchhaltevermögen und deine Erklärung. Jetzt hast du dir den Stern aber auch redlich verdient.
Es geht ja bei der Aufgabe um folgendes:
Es lassen sich leicht Beispiele finden, bei denen Dijkstra versagt, wenn es negative Kantengewichte gibt (ob nun alle negativ sind oder nur eines ist dabei egal).
Nun könnte man einfach sagen: Egal, ich erhöhe einfach alle Kantengewichte so, dass hinterher alle positiv sind, bestimme dann mit Dijkstra einen kürzesten Weg auf dem Graphen mit den neuen - jetzt positiven - Kantengewichten und ziehe dann hinterher wieder einfach wieder diesen Wert, um den ich vorher erhöht habe, ab.
Geht das? Und warum? Oder geht das nicht? Warum nicht?
Das ist die Frage der Aufgabe. Und da man einen Beispielgraph angeben soll, wird es wohl NICHT einfach gehen und man kann das an einem Gegenbeispiel zeigen.