Übung 06: Graphentheorie

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Gegeben sei der folgende Digraph mit 9 Knoten, 15 Pfeilen, einer Quelle (Knoten 1) und einer Senke (Knoten 9):

  1. Geben Sie hierzu die kompakte Speicherung an (Felder AA, BB, CC und DD).
  2. Bestimmen Sie mit dem FIFO-Algorithmus die kürzesten Wege von Knoten 1 zu allen anderen Knoten.
  3. Überprüfen Sie Ihre Lösungen mit Julia.

Ihre Lösung in Julia

Die Handrechnung können Sie mit einem kleinen Optimierungsmodell prüfen: Der kürzeste Weg von Knoten 1 zu Knoten 9 lässt sich als Flussproblem formulieren (vgl. Vorlesung 6): eine Flusseinheit verlässt die Quelle, eine erreicht die Senke, an allen anderen Knoten gilt Flusserhaltung. Nennen Sie Ihr Modell modell:

using JuMP, HiGHS

kanten = [(1,2,55), (1,3,15), (2,5,16), (3,4,12), (3,6,42),
          (4,2,11), (4,5,30), (4,6,16), (4,7,40), (5,7,11),
          (5,8,45), (6,9,62), (7,8,17), (7,9,31), (8,9,13)]

modell = Model(HiGHS.Optimizer)
set_silent(modell)

# IHR CODE HIER

optimize!(modell)
# Führen Sie diese Zelle nach Ihrer Lösung aus:
@assert isapprox(objective_value(modell), 95.0; atol = 1e-4) "Noch nicht korrekt. Prüfen Sie die Flusserhaltung an den Zwischenknoten."
println("Kürzester Weg von 1 nach 9 korrekt: Länge = ", objective_value(modell))
HinweisWeitere Knoten prüfen

Ihre FIFO-Entfernungen zu den übrigen Knoten prüfen Sie, indem Sie die Senke im Modell austauschen (z. B. Knoten 7 statt Knoten 9) und erneut lösen.