Ford-Fulkerson Algorithmus bzw Max-Flow-Problem
-
Hi!
Ich arbeite gerade an einem Programm was u.A. den längsten Weg in einem Graph feststellen soll.
Dazu gibt es den netten Ford-Fulkerson Algorithmus.
Leider blicke ich da überhaupt nicht durch mit dem was ich so gefunden hab.
Hat vielleicht einer von euch einen brauchbaren Quelltext dazu?
Vielen Dank im Voraus.
-
Hallo,
das passt besser nach RUDP.
-
ja gut,
Ich suche halt nach einem Quelltext in C++.
Aber wenns das hier auch gibt
...
-
Vielleicht hilft dir dieser Code weiter(ist aber Java):
http://wwwiti.cs.uni-magdeburg.de/iti_db/algoj/abb/abb-16.28.eps ab 16.28
Theorie gibts hier: http://www-lehre.informatik.uni-osnabrueck.de/~graph/skript/8_3_Algorithmus_von.htmlRate mal wo ich diese Infos her habe
MfG SideWinder
-
Ja, ich google schon seit 2 Tagen.
Und der Java scheiss hilft mir leider überhaupt nicht.
Trotzdem Danke!
-
obergott schrieb:
Hi!
Ich arbeite gerade an einem Programm was u.A. den längsten Weg in einem Graph feststellen soll.
Dazu gibt es den netten Ford-Fulkerson Algorithmus.
Leider blicke ich da überhaupt nicht durch mit dem was ich so gefunden hab.
Hat vielleicht einer von euch einen brauchbaren Quelltext dazu?
Vielen Dank im Voraus.
Ford-Fulkerson? Der berechnet doch die kürzesten Wege zwischen zwei Punkten.
Oder gibt es noch einen anderen Ford-Fulkerson-Algorithmus? Falls ja, welche Laufzeit hat dieser dann? (Längster Weg zwischen zwei beliebigen Punkten ist glaube ich NP-vollständig).Gruß,
Niddhogg
-
Nein, es gibt nur einen.
Der Ford-Fulkerson-Algorithmus berrechnet in einem Netzwerk den längsten bzw. schwersten Weg über Kanten von Quelle nach Senke.
-
Hallo obergott,
da habe ich wohl den Ford-Fulkerson mit dem Floyd-Warshall bei den kürzesten Wegen verwechselt.
Wir haben im letzten Semester den Ford-Fulkerson auch "nur" in Java und unter Benutzung einer speziellen Library für Graphen/Netzwerke implementiert. Den Quellcode hätte ich, dürfte Dir aber wahrscheinlich nich so sehr weiterhelfen?!?
Wenns um den Algorithmus an sich geht, dann ist vielleicht ein Blick in das Skript(PDF)
hilfreich, ab S.149. Auf S.152 steht z.B. der Ford-Fulkerson ausführlich als Pseudocode und kurz dahinter ist auch ein einfaches Beispielnetzwerk "durchgerechnet" (also Bestimmung maxFlow bzw. minCut).
Anhand des Skriptes ging die Implementation bei uns eigentlich recht gut.Gruß,
Niddhogg
-
Jo, ok Danke
Ich schau mal wie ich das umsetzen kann.