Graphalgorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:57 Mo 14.03.2005 | | Autor: | sunita |
Hallo Leute,
Ich brauche eure Hilfe, um die wichtige Teil Graphalgorithmus zu verstehen: wie funktioniert genau FLOYD WARSHALL ALGORITHMUS?
und
Maximum Fluß- Probleme: Wie wählt man Fluß, um max Fluß zu erreichen? Hat die Kapazität der Kante eine Entscheidende Rolle? weiß allerdings nicht wie ich es eindeutig formulieren soll.
Vielen Dank.
Sunita.
|
|
| |
|
Hallo Sunita,
ich habe derzeit nicht den Floyd Warshall Algorithmus zur Hand. Vielleicht kannst du ihn hier einfach nochmal posten und dann genau bezeichnen was dir eigentlich unklar ist.
Weißt du was ein maximaler Fluss ist? Hast du Schwierigkeiten mit Graphen oder ist da alles bekannt.
Zum Thema maximaler Fluss fällt mir sofort ein, dass der maximal auch über den minimalen Schnitt berechnet werden kann.
Am besten konkretisierst du nochmal, vielleicht hast du ja auch ein Beispiel, und hast schon einen Teil bearbeitet.
Die Kapazität ist insofern relevant, als dass damit die maximale Anzahl von Einheiten festlegt, z.B. bei einem Rohr, besagt die maximale Kapazität, dass z.B. 10 Liter zur Zeit durchfließen können. Dann könnten nur 8 durchfließen, aber auf keinen Fall 12.
Gruß
marthasmith
|
|
|
| |
|
| Status: |
(Frage) für Interessierte  | | Datum: | 16:02 Di 15.03.2005 | | Autor: | sunita |
Hallo Marthasmith,
Vielen Dank für deine Aufmerksamkeit.
Floyd-Warshall Algo, betrachtet min kürzeste Wege, mehr weiss ich leider auch nicht. Ich habe nur eine einzige Folie aus der Vorlesung mit der rekursive Definition dazu.
Leider ist so schwierieg ohne Bezeichnungen eine klare Frage zu stellen.
anders Beispiel:
1
s p
2
stellst dir mal vor: 5 Kanten((s,1)=1, (s,2)=4, (1,2)=2, (1,p)=5, (p,2)=3 Kanten und Gewicht, die 4 Knoten S, P, 1 und 2 verbinden.
Wie werde ich schritt für schritt das max Fluss erreichen.
mein Fluss sollte maxi <=5 .
Erstmal nehme ich mein min-spannbaum wäre mit KantenVon s1,2,3 zum Ziel p, dann gebe ich erstmal F=1.. bis F=4 nur meine Kante für maxi F=4 sind nicht mehr meine Spannbaum, sonder 4,2,3. Ist das in Ordnung?
wäre toll, wenn dieses Mal habe ich mich besser meine Schwieriegkeit gemalt habe.
Chöne Grüße.
Sunita
|
|
|
|
