---

Geschrieben von Karlito am 17.09.2013 um 11:50:

 

Naja, ganz einfach finde ich die Aufgabe nicht. Vor allem ist ja bisher noch nicht gezeigt, dass ein Schichtgraph entsteht. Ich tu mich mit Beweisen auch immer schwer und bin deshalb froh, dass ich die betreffenden Klausuren bisher alle bestanden habe.

VG,

Karlito

---

Geschrieben von deppensido am 17.09.2013 um 14:22:

 

hallo,

zur Übung hab ich mich noch an einer ähnlichen Aufgabe versucht (ist die letzte, die ich habe). Bei der Aufgabe hat man ein Straßennetz als gewichteter gerichteter Graph gegeben. Die Kantengewichte geben dabei die Steigung der Straßen an (soll ein Straßennetz der Alpen sein), negative Kantengewichte sind Gefälle. Die Aufgabe lautet nun: Modifizieren Sie Dijkstras Algo., so dass dieser alle Wege mit kleinster maximaler Steigung von einem Startort s zu allen anderen Orten in den Alpen berechnet. Zusätzlich soll man begründen, warum in diesem Fall negative Kantengewichte kein Problem sind.

Was heißt hier: "mit kleinster maximaler Steigung"? Müssen alle berechneten Distanzen positiv sein oder dürfen Kanten mit negativen Kantengewichten nicht betrachtet werden? Der Dijkstra Algo. berechnet ja für einen gewichteten Graphen (ohne negativen Kantengewichte) kürzeste Wege von s zu allen anderen Knoten. Meine Idee wär deshalb: statt
d[v]<-d[u]+w(u,v) berechne d[v]<- |d[u] | + |w(u,v)|. Also einfach d[u] und w(u,v) in Betragsstriche setzen.

Grüße