(N=Knoten, A=Kanten)

(A=Angebotsort, B=Bedarfsort, c=Kosten, )

Kette: Folge von Kanten die mit Knoten verbunden sind

Weg: gerichtet: begehbarer Weg, ungerichtet: Kette

Top sor: wenn N so numeriert sind, daß für jede Kante (i,j) gilt i<j

Greedy: Lösung wird schrittweise aufgebaut, Entscheidungen werde nicht revidiert

Nach Greedy Methode, für MSB in ungerichteten Graphen

Die Kanten werden in der Reihenfolge nichtfallender (steigender) Gewichte gefärbt. Eine Kante, deren beide Endknoten im gleichen blauen Baum liegen, wird rot gefärbt, sonst blau.

Aufwand: O(|A| log |A|)

Nach Greedy Methode, für MSB in ungerichteten Graphen

Ausgehend von eineme festen Knoten s wird ein einziger blaugefärbter Baum schrittweise aufgebaut. Ist T dieser blaugefärbte Baum, so färbt der nächste Schritt eine Kante mit minimalem Gewicht blau, die T mit einem Knoten i nicht elm. T außerhalb von T verbindet.

Dazu wird der Graph in 3 Teile aufgeteilt: Knotenmenge T (Knoten von N die bereits in T sind), Knotenmenge G (Knoten von N die Grenzen zu T sind) und R (Restmenge). Bei jedem Schritt wird ein Knoten von G zu T gefuegt.

Aufwand: O(|A| log |N|)

ähnlich Greedy/Prim Methode, kürzeste Wege, alle Längen sind nicht negativ, Zyklen sind zulässig, für kürzeste Wege von einem festen Knoten s zu allen anderen Knoten, LabelSetting

Graph wird in 3 Teilmengen unterteilt:

Bei jedem Schritt wird ein Knoten i aus B mit kleinstem temporären Lagel gewählt und sein Label als permanent erklärt und somit A zugeordnet. Alle seine direkten Nachfolger werden dann temporär gelabelt, bzw. ihre temporären Labels werden gegenenfalls korrigiert. Der Prozeß wird solange wdh. bis keine temporären Labels mehr vorhanden sind.

Vorgehen: tue s in B, temporär 0, alle anderen erhalten infinity, solange B nicht leer, wdh., nimm elem aus B mit kleinstem Gewicht, mache dieses permanent, berechne die Gewichte aller Nachfolger von elem und tue diese in B

Aufwand: O(|A| log |N|) worstcase ist O(n²) bzw. O(n³) für kürzeste Wege von allen zu allen

Ergebnis: Ist Knoten i von 1 aus erreichbar, so enthält d[i] die kürzeste Entfernung von 1 nach i, ansonsten ist d[i]=infinity.

LC Verfahren sind Ls überlegen, wenn ihr Repetierfaktor in der Nähe von 1 liegt.

FIFO-LC Verfahren, kann auch negativ bewertete Kanten verarbeite, aber keine Zyklen negativer Länge, kürzeste Wege von einem festen Knoten s zu allen anderen Knoten,

Verfahren wie beim Dijkstra, nur werden hier kein Knoten permanent markiert, sondern alle nur temporär. Wird das Label eines Knotens zum ersten Mal gesetzt oder verbessert, so wird er in eine Liste, die wir mit B bezeichnen, hineingelegt. Die Bearbeitung eines Knotens dieser Liste B erfolgt dann, indem das (temporäre) Label eines jeden seiner nächsten Nachfolger gesetzt bzw. falls möglich verbessert wird. Das Verfahren terminiert, sobald B leer ist.

Vergehen: wie beschrieben, initialisierung wie bei Dijkstra

Aufwand: O(|N| * |A|)

Ergebnis: wie oben

Die FIFO-Strategie für zu obigem schlechten Verhalten. Folgende Strategie (FIFO und LIFO) von d'Esopo und Pape führt zu einem guten Laufzeitverhalten, bei gleichem WorstCase.

Ein gerade markierter Knoten wird an das Ende der Liste angefügt, wenn er erstmals markiert wurde. Falls i wdh. markiert wird, so wird er am Anfang der Liste eingefügt.

Gehört zu LC-Verfahren, liefert kürzeste Entfernung zwischen allen Paaren von Knoten, Zyklen negativer Länge dürfen nicht auftreten, ansonsten können auch negative Kanten bearbeitet werden.

Matrix, mit allen Wegen, von i nach j,

Graph mit 6 Knoten, bau 6x6 Matrix, in Felder mit infinity initialisieren, in die Matrix, die Kantengewichte die ex sind. Dann fang an: jeden Knoten betrachten, von D1 bis D6,

O(n³)

längste Wege: alle Kantengewichte negieren und kürzeste Wege suchen

Alle Knoten mit 0 initialisieren, dann Knotenwert(i:=indegree) auf # eingehender Pfeile setzen. Liste der Knoten ohne Vorgänger (mit i=0) erstellen. Alg. terminiert, falls Liste leer. Wurden dann weniger Knoten aus der Liste geholt, als insg. vorhanden sind, so hat der Graph Zyklen. Jetzt werden nach und nach die Knoten aus der Liste geholt und in TO[i] geschrieben. Jedesmal wird dabei das i der Knoten, die von diesem Knoten erreichbar sind um 1 gesenkt, erreicht ein i dabei 0 wird es in die Liste geschrieben.

O(m)

Graph azyklisch, negativ bewertete Kanten dürfen vorkommen, aber keine Zyklen negativer Laenge, LC-Verfahren

alle Knotengewichte mit infinity initialisieren, bis auf den Startknoten, dieser erhaelt null, erste Element aus TO[] entfernen, für alle Nachfolger dieses Knotens Kantengewicht ermitteln und notfalls korrigieren, solange, bis TO[] leer ist.

Aufwand: O(m)

Flußprobleme:

c,ij:= Kosten für diese Kante

u,ij:= obere Flußschranke

l,ij:= untere Flußschranke

b:= Bewertung des Knotens: b<0 = Bedarfsknoten, b>0 = Anbieterknoten, sonst Umladeknoten

Transhipment-Problem -> s-t-Flußproblem:

Führe Superquelle s und Supersenke t ein.

Kürzeste Wege Problem:

Spezialfall s-t, alle b(i) auf 0, b(s) auf 1 und b(t) auf -1

Unk./kap. Transportproblem:

Netzwerk aus N1 Anbietern und N2 Nachfragern,

Mehrstufiges Transportproblem:

N besteht aus Ns, Nt und Nd, Ns=Anbieger, Nd=Nachfrager, Nt=TransshipmentKnoten

Zirkulationsflüsse:

Alle Knoten sind Umladeknoten, neue Kante von t nach s, mit der entsp. Kapazität

Kapazitätsrestriktionen auf Knoten:

Knotenaufspaltung, neue Kante: Kosten = 0, upper und lower Grenze auf Restriktion

Feasible-Flow-Problem:

Ist es moeglich alle Nachfragen von allen Anbietern zu befrieden?

A) Führe s und t ein, Reduziere die |Knotengewichte| entsprechend und baue entsprechenden Kantengewichte, nun loese das Problem

B) schicke soviel über alle Kanten, daß alle Unteren Grenzen verschwinden.

C) ??? (S72/73)

Ford & Fulkerson:

Zur Terminierung vorausgesetzt: nur Ints. Keinen Weg von s nach t mit nur Kanten unendlicher Kapazität beinhaltet. Ferner wird das Netz symmetrisch gemacht.

Restflußnetzwerk:

Die Restkapazität für jede Kante ist die max. Größe des zusätzlichen Flusses, der von i nach j geschickt werden kann. Dabei inuziert der Abbau eines Flusses durch (j,i) eine Flußvergrößerung von i nach j. Somit enhält das Restflußnetzwerk genau die Kanten, worüber man einen Fluß positiver Größe schicken kann.