Maximale Flüsse in einem Graphen

Seminarthema 10 präsentiert von David Ruitter

Flussnetzwerk

Quelle

Ziel

Alle Knoten benennen

Kapazitäten

Fluss

Augmentierender Pfad

Q

Verbleibende Kapazität einer Kante

=

Kapazität - Fluss

Ford-Fulkerson Verfahren

Solange es noch augmentierende Pfade gibt

  1. Wähle augmentierenden Pfad aus
  2. Finde die geringste verbleibende Kapazität im augmentierenden Pfad (Bottleneck)
  3. Erhöhe den Fluss aller Kanten um den Wert des Bottlenecks
  4. Füge den Wert des Bottlenecks zum Gesamtfluss hinzu

Title: Pseudocode Ford Fulkerson Verfahren, Attribution: abgeändert nach Saake und Sattler 2006 vgl. Algorithmen und Datenstrukturen Eine Einführung mit Java

Kein Algorithmus, da

Nicht vorgegeben wird, mit welchem Suchverfahren der augmentierende Pfad zu suchen ist
Source: Algorithmen und Datenstrukturen Eine Einführung mit Java Saake und Sattler 2006 vgl. S. 456
Sedgewick, R. und Wayne, K. (2014). Algorithmen Algorithmen und Datenstrukturen. Pearson Deutschland GmbH, München, vierte. Auflage. vgl. S. 938

Edmonds-Karp Algorithmus

Ford-Fulkerson mit Breitensuche als Suchverfahren
Source: Sedgewick, R. und Wayne, K. (2014). Algorithmen Algorithmen und Datenstrukturen. Pearson Deutschland GmbH, München, vierte. Auflage. vgl. S. 941

Breitensuche

Breitensuche

Queue
Q
Explored
Q
Source: Sedgewick, R. und Wayne, K. (2014). Algorithmen Algorithmen und Datenstrukturen. Pearson Deutschland GmbH, München, vierte. Auflage, vgl. S. 577 f.

Laufzeitkomplexität

O(|V ||E|²)

Cormen, T. H., Leiserson, C. E., und Ronald L. Rivest, C. S. (2003). Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, zweite Auflage. vgl. S. 661

Implementierung in Java

Java Klassen

Implementierung in Java

						
							public static int maxFlow(Flownetwork flownetwork) {
								List pathToSink;
								int totalFlow = 0;
								while(!(pathToSink = flownetwork.getAugmentingPath())
									.isEmpty()) {
									// Erhöhen des totalFlows um path Bottleneck
									...
								}
						
								return totalFlow;
							}

Implementierung in Java

						
							public List getAugmentingPath() {
								var queue = new ArrayDeque();
								var explored = new HashSet();
								// Key is the child vertex and value the parent of the child
								var childParent = new HashMap();
								
								queue.offer(source);
								explored.add(source.getLabel());
								
								while(!queue.isEmpty()) {
									Vertex currentVertex = queue.poll();
									
									// Pfad rekonstruieren sobald gefunden
									...

									Collection edgesFromCurrentVertex = currentVertex.getEdges();
									for (Edge edge : edgesFromCurrentVertex)
										if (edge.hasRemainingCapacity() &&
											!explored.contains(edge.to().getLabel())) {
											queue.push(edge.to());
											explored.add(edge.to().getLabel());
											childParent.put(edge.to(), edge.from());
										}			
								}
								
								return List.of();
							}

Visualisierung

Gesamtfluss:  0
Maximal möglicher Fluss:  0