Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
9. uebungsblatt → rechneruebung 16
hi,
wollte mich mal an obengenannte aufgabe machen, bei der man eine methode shortestPath (int source, int target) schreiben soll, und zwar mit dem algorithmus von ford/fulkerson.
kann es sein, dass die sich verschrieben haben, weil soweit ich weiss, berechnet der ford/fulkerson einen maximalen durchfluss und keinen kuerzesten weg?! das muesste dann der bellman/ford sein, oder?
sedgewick sagt: Ford-Fulkerson dient zur berechnung des maximalen flusses eines netzwerkes. du hast also recht 
mir ist noch eine andere formulierungen sauer aufgestossen,
es ist die rede von einer menge U, und dann soll darauf die FIFO strategie angewendet werden?! :vogel: LOL 
ja, das hab ich auch nicht gecheckt! was hat das zum teufel mit dem algorithmus zu tun?
die dokumentation desselben im skript ist auch mehr als duerftig: da werden irgendwelche i’s und n’s verwendet, die nie eingefuehrt worden sind und namen verwechselt, das koennte mich echt aufregen! dafuer ist jetzt meine implementation gescheit ineffizient schmoll. 
hmm. ich hab das neunte noch nicht gemacht (in fact, das achte und siebente auch net, sollte ich wohl mal… :-/ ).
hehe, nein, das ist nicht mein punkt.
in einer menge gibt es kein erstes element. FIFO erfordert aber, dass das erste element, das reingekommen ist, das erste ist, das wieder rauskommt. 
=> menge := warteschlange ? stimmt auch net. es ist schlicht falsch, in diesem kontext von einer menge zu sprechen.
ok, soetwas wuerde mir erstmal ueberhaupt nicht auffallen. ich hab nur gesehen, dass das nicht zum algorithmus gehoert, so, wie er im skript steht. und bei dem versuch, eben jenen zu implementieren, hab ich auch gemerkt, dass man ihn aus den skriptinfos gar nicht konstruieren kann, weil die infos dort so lueckenhaft sind.
also, ich hab mir jetzt nochmal die aufgabe 21 angeschaut von jemandem, der im gegensatz zu mir in der algouebung war (thx@captain!). da geht es um dasselbe, man soll den kuerzesten weg bestimmen. in dem fall ist das sogar fast richtig, weil man aus der MENGE, die meistens aus mehreren knoten besteht, einen raussuchen und weiteruntersuchen muss. WELCHEN man nimmt, haengt von der strategie ab. in der a) soll man das am laengsten in der „menge“ vorhandene element nehmen (= fifo, queue), und in der b) denjenigen knoten, der bis jetzt die geringsten gesamtwegkosten hat (= perfekte auswahl).
ich hak das jetzt einfach ab.
ich verstehe. die meinen also nicht ne echte menge, sondern die menge, die zufällig auch so heisst? :-p das ist der punkt, der begriff menge hat eine ganz präzise bedeutung. wenn se also menge schreiben, dann sagen sie eigentlich viel mehr als nur dieses eine wort.
eine eindeutige formulierung würde mir lieber sein (ich bin erbsenzähler). wenn du sowas in der klausur schreibst, wette ich mit dir, dass du nicht die volle punktzahl der aufgabe zugesprochen bekommst.