Algorithmen

Question 1

Vorgehen Topologische Sortierung

Answer 1

0. Stelle eine Tabelle auf mit allen Knoten und der Anzahl der Vorgänger
1. Wähle einen Knoten mit 0 Vorgängern aus
2. setze diesen knoten auf -1
3. ziehe von allen Nachfolgern 1 ab
4. -> Schritt 1

Reihnfolge in der die -1 erreicht wird ist topologische Sortierung

Question 2

Ziel: Algorithmus von Ford und Fulkerson

Answer 2

maximalen Fluss im Netzwerk

Question 3

Ziel: Cycle-Cancelling Algorithmus

Answer 3

maximalen Fluss mit minimalen Kosten

Question 4

Ziel: Dijkstra - Algorithmus

Answer 4

kürzesten Weg zwischen zwei Punkten, wenn es keine negativen Kantengewichte gibt

Question 5

Ziel: Generischer Label Correcting Algorithmus

Answer 5

kürzesten Weg zwischen zwei Punkten, auch(!) wenn es negative Kantengewichte gibt. Aber anfällig für negative Zykel

Question 6

Kürzeste Wege Problem

Answer 6

• Dijkstra, Cycle-Cancelling (falls negative Kantengewichte)

- Knoten haben generell kein Gewicht, außer als Ausschlusskriterium (Bsw. Kumulierte Kosten -> Budgeteinhaltung)

Question 7

Wahrscheinlichkeiten

Answer 7

Logarithmus im Graph für Additivität

Question 8

Wieso kann der Dijkstra Algorithmus keine negativen Kantengewichte verarbeiten?

Answer 8

permanent markierte Knoten können nicht mehr verändert werden

Question 9

Vorgehen Dijkstra

Answer 9

• Tabelle erstellen mit allen Knoten (zeilen) pred und init (0 für Start unendlich für Rest)
• Knoten vom Start aus “entdecken”
• vom Knoten mit der geringsten Gewichtung weitererkunden
• bereits entdeckte Knoten evtl. korrigieren

Question 10

Vorgehen Label Correcting

Answer 10

• Start auswählen
• alle anderen Knoten auf unendlich setzen
• in einer Phase alle(!) Kanten überprüfen, ob ein Knotenwert nach unten korrigiert werden kann.
• ein Graph mit n Knoten wird in n+1 Phasen abgearbeitet

Question 11

Vorgehen Ford Fulkerson

Answer 11

• Setzte Start- und Zielknoten
• Setzte den Fluss an jeder Kante = 0
• Suche einen augumentierten Pfad und erhöhe bis zum Maximum
• bis kein augumentierter Pfad mehr da ist

Question 12

Vorgehen Cylcle-Canceling- Algorithmus

Answer 12

Voraussetzung: Residualgraph b-Fluss (mit Kosten)

1. Finde negativen Zirkel (Kosten)
2. erhöhe den Zirkel um die engpasskapaziät
3. solange bis man keinen negativen zirkel mehr findet

-> zirkel kann auch mehr als 3 Knoten enthalten

Question 13

Minimalkostenfluss

Answer 13

• Wert des Flusses ist durch Bedarfe und Angebote (b-Werte) vorgegeben. Dieser Fluss soll durch den Cycle Canceling Algorithmus maximiert werden.
• Fluss kann an mehreren Knoten entspringen
• Kosten und Kapazitäten an den Kanten
• b-Werte an den Knoten

Question 14

Maximalfluss

Answer 14

• Fluss nicht vorgegeben, maximaler Fluss wird gesucht
• Fluss entspringt an einer Quelle und geht in eine Senke
• Nur Kapazitäten an den Kanten

Question 15

Maximalflussprobleme

Answer 15

Zuordnungsprobleme, Transportprobleme

Question 16

Kürzeste-Wege-Probleme

Answer 16

Zeitexpansion, Raumprobleme, Überdeckungsprobleme

Question 17

Minimaler-Schnitt-Probleme

Answer 17

(Kosten, Kapazitäten) an den Kanten

an den Knoten b-Werte