Shortest Path in einem Graphen

Wissenschaft Informatik
#1

Hallo,
ich haette mal eine Frage zu dem kueresten Weg in einem Graphen. In dem Buch Introduction to Algorithms wird ein beschrieben,
dass es Kanten und Knoten gibt, die negativ sind. Meine Fragen: Warum sind denn negative Wert zugelassen? Warum sind Knoten gewichtet?
Z.B. beim Routenplaner sind doch solche Sachen nicht zugelassen? In welchen Anwendungen werden die kuerzesten Wege berechnet, die Knotengewichtung
und negative Kantenwerte gibt? Bin da ein bisschen verwirrt, da das Shortest Path-Kapitel in dem Buch mit einem Routenplanbeispiel von Chicago nach Bosten angefangen hat.

Felix

#2

Hallo Felix,

kannst du evtl. noch etwas genauer beschreiben, wie in dem Buch der Alg. motiviert wurde ?

Für mich hört sich das im Zusammenhang mit kürzesten Wegen etwas seltsam an.
Wird der Wert eines Wege nur durch die Anzahl der besuchten Knoten gerechnet ? Oder soll über die Werte an den Kanten minimiert werden ? Dann ist bei negativen Kantengewichten darauf zu achten, dass der Graph zyklenfrei ist (was bei eh nur bei gereichteten Graphen funktioniert).

Könnten die negativen Knotenwerte vielleicht im Rahmen eines Beispiels Zwischenergebnisse darstellen (im Sinne von: Knoten x kann (bisher) mit einem Wert von y erreicht werden) ?

Gib doch noch ein paar Infos.

Hartmut

P.S. Handelt es sich um das Buch von Cormen ? Wenn ja, dann schick doch bitte die Seitenzahl.

#3

Hi Hartmut,

werde heute die Infos reinposten!

Felix

#4

Hi Felix,
ich vermute mal, dass Du in Cormen, Leiserson, Rivest geschmoekerst hast - ein gutes Buch! Eigentlich ist das Buch fuer Dein Problem nebensaechlich, sollte aber Deine Frage beantworten.

Ich habe Deine Frage jetzt so verstanden, dass Dir unklar ist wozu man negative Kanten in einem Graphen benoetigt und welche Rolle die im „Kuerzeste-Wege-Problem“ spielen und antworte jetzt einfach mal darauf.

Die Gewichte im Graphen muessen nicht immer unbedingt Entfernungen darstellen, sondern koennten z.B. auch Kosten oder Gewinne modellieren. Die Knoten sind zum Beispiel Meilensteine in einem Projekt, die Kanten verkoerpern Prozesse, welche im Projekt durchlaufen werden muessen bzw. koennen. Gesucht ist ein Kostenminimaler Weg (Prozessablauf) von A (Projektstart) nach B (Projektende).
So lassen sich eine Vielzahl von Anwendungsmoeglichkeiten finden, in denen negative Gewichte eine Rolle spielen!

Einige Algorithmen (zum Beispiel der von Dijkstra) arbeiten nicht korrekt, wenn sie auf Graphen mit Kantengewichten kleiner 0 losgelassen werden. Ein entsprechender Beweis muesste in Deinem Buch zu finden sein. Eigentlich brauchst Du Dir nur ein Beispiel zu konstruieren. (Zum Beispiel folgender Graph mit drei gerichteten Kanten ((A,B,2),(A,C,3),(B,C,-2)). (Beschreibung einer Kante: (Anfangsknoten, Endknoten, Gewicht) Gesucht ist der kuerzeste Weg von A nach C. Der Algorithmus von Dijkstra wuerde den Weg (A,B) mit der Gewichtssumme 2 liefern, welches natuerlich falsch ist.
Andere Algorithmen (zum Beispiel der von Moore) kommen mit negativen Kanten klar, benoetigen aber mehr Rechenzeit. (Dijkstra O(|V|^2), Moore O(|V|^3) V ist die Knotenmenge des Graphen. )
So nun ist die Lehrbuchstunde beendet.
Hoffentlich hat es geholfen?
Gruss Jan

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#5

Hallo Hartmut!
Sorry, dass ich mich nicht mehr gemeldet habe. Hatte das Forum vergessen. Hab die Infos aus einem neuen Forum geholt. Wenn es Dich noch interssiert. In dem Buch von Rivest, Cormen, etc. steht die Motivation mit negativen Kantengewichten auf Seite 515.

Felix

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]