Dijkstras?

Wissenschaft Informatik
#1

Hallo, kann ich bei folgendem Problem den Dijkstras anweden?
Es klingt verdammt danach, bin mir aber nicht sicher…

Ein Unternehmen für Schwertransporte ist bestrebt, für seine Lastwagen Routen mit einer möglichst geringen maximalen Steigung zu finden, da sich die Ladekapazität nach der maximalen Steigung entlang eines Weges richtet. Wir stellen ein Straßennetz wieder als einen gerichteten Graphen G=(V,E) dar. Die Straßen(gerichtete Kanten) sind mit der maximalen Steigung dieser Straße beshcriftet. Es gibt keine ngeativen Kantenbeschriftungen, Straßen mit Gefälle werden mit 0 beschriftet, da die Ladekapazität hier so hoch ist wiefür ebene Straßen. Dien Zentrale der Firma liege im Knoten S Element V.

Die Wege mit gerinsgter maximalen Steigung von S zu allen anderen Knoten sind zu bestimmen. Es soll ein möglichst effizienter Algo entworfen werden…natürlich mit Korrektheit und LAufzeit.

Wie gesagt, ich denke, dass man den Dijkstras anweden kann?

grüße

#2

Auch hallo.

Die Wege mit gerinsgter maximalen Steigung von S zu allen
anderen Knoten sind zu bestimmen. Es soll ein möglichst
effizienter Algo entworfen werden…natürlich mit Korrektheit
und LAufzeit.

Klingt nach Graphentheorie und kürzesten Wegen. Und fällt
unter ‚Operations Research‘ (oder Numerik): https://gor.uni-paderborn.de/60_ORLinks/
Mit Begriffen wie Quelle und Senke braucht man hier jedenfalls nicht anzukommen…

Wie gesagt, ich denke, dass man den Dijkstras anweden kann?

Ja.

HTH
mfg M.L.

#3

Hi
Dijkstras Algorithmus addiert die ‚Entfernungen‘, hier geht es allerdings um das Maximum. So eins zu eins kann man das also schon mal nicht anwenden.

Es wäre aber zu prüfen, ob Dijkstra mit einer modifizierten ‚Addition‘ funktioniert, bei der a + b = max(a,b).

Ich vermute das geht, aber das ist halt nur eine Vermutung.

#4

Hallo!

Ja, man kann den Algorithmus von Dijkstra dazu benutzen. Man muss nur die Kantengewichte so wählen, dass das Benutzen einer Kante mit hoher Steigung den Weg teurer macht als jeder andere Weg, der nur Kanten mit niedrigerer Steigung benutzt, also im schlimmsten Fall immer „Steigung eins weniger“.

Wenn man zum Beispiel annimmt, dass es 5 Steigungen gibt und dein Graph m Kanten hat (das beschränkt die maximale Länge eines Weges nach oben), so könnte man also Kantengewichte (m+1)^(steigung) wählen. Selbst ein Weg mit m Kanten und Steigung k-1 wäre dann billiger als ein Weg über nur eine Kante mit Steigung k.

Viele Grüße,
Olaf

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