Vorgehen Topologische Sortierung
- Stelle eine Tabelle auf mit allen Knoten und der Anzahl der Vorgänger
- Wähle einen Knoten mit 0 Vorgängern aus
- setze diesen knoten auf -1
- ziehe von allen Nachfolgern 1 ab
- -> Schritt 1
Reihnfolge in der die -1 erreicht wird ist topologische Sortierung
Ziel: Algorithmus von Ford und Fulkerson
maximalen Fluss im Netzwerk
Ziel: Cycle-Cancelling Algorithmus
maximalen Fluss mit minimalen Kosten
Ziel: Dijkstra - Algorithmus
kürzesten Weg zwischen zwei Punkten, wenn es keine negativen Kantengewichte gibt
Ziel: Generischer Label Correcting Algorithmus
kürzesten Weg zwischen zwei Punkten, auch(!) wenn es negative Kantengewichte gibt. Aber anfällig für negative Zykel
Kürzeste Wege Problem
- Dijkstra, Cycle-Cancelling (falls negative Kantengewichte)
- Knoten haben generell kein Gewicht, außer als Ausschlusskriterium (Bsw. Kumulierte Kosten -> Budgeteinhaltung)
Wahrscheinlichkeiten
Logarithmus im Graph für Additivität
Wieso kann der Dijkstra Algorithmus keine negativen Kantengewichte verarbeiten?
permanent markierte Knoten können nicht mehr verändert werden
Vorgehen Dijkstra
- 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
Vorgehen Label Correcting
- 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
Vorgehen Ford Fulkerson
- 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
Vorgehen Cylcle-Canceling- Algorithmus
Voraussetzung: Residualgraph b-Fluss (mit Kosten)
- Finde negativen Zirkel (Kosten)
- erhöhe den Zirkel um die engpasskapaziät
- solange bis man keinen negativen zirkel mehr findet
-> zirkel kann auch mehr als 3 Knoten enthalten
Minimalkostenfluss
- 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
Maximalfluss
- Fluss nicht vorgegeben, maximaler Fluss wird gesucht
- Fluss entspringt an einer Quelle und geht in eine Senke
- Nur Kapazitäten an den Kanten
Maximalflussprobleme
Zuordnungsprobleme, Transportprobleme
Kürzeste-Wege-Probleme
Zeitexpansion, Raumprobleme, Überdeckungsprobleme
Minimaler-Schnitt-Probleme
(Kosten, Kapazitäten) an den Kanten
an den Knoten b-Werte
