Not logged in. · Lost password · Register

Page:  1  2  next 
Famous
Member since Oct 2011
70 posts
Subject: Klausur 02.08.12 Algo von Floyd
Hallo,

ich hab gerade versucht, die Tabelle aus der letzten Klausur nach dem Algo von Floyd auszufüllen.
Jedoch habe ich gar keine Anhaltspunkte, wie das funktionieren soll, denn weder in den Vorlesungsfolien noch im Internet habe ich Bspiele gefunden.
Vielen Dank!
kronos
Lord of Time :-)
Member since Oct 2012
352 posts
https://www2.cs.fau.de/teaching/WS2012/AuD/slides/secure/a…
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algori…

In Introduction to Alogrithms von Cormen sollte es auch drin sein.
Famous
Member since Oct 2011
70 posts
Das alles sagt mir aber nichts :(
John Late
johnLate
Member since Oct 2009
688 posts
Du hast also im Wikipedia-Artikel links auf "Deutsch" geklickt, und selbst dort nichts verstanden?
Allen ist das Denken erlaubt, vielen bleibt es erspart.
Ina89
Member since Jun 2012
34 posts
+1 Famous
Hier die ausgefüllte Floyd-Tabelle aus der Klausur, wie es meiner Meinung nach aussehen müsste.

Mit rot habe ich jeweils das Minimum gekennzeichnet.

Hoffe, ich konnte dir ein bisschen helfen :)

[Image: "Floyd.jpg"]
The author has attached one file to this post:
Floyd.jpg | Save   34.8 kBytes
Image
Famous
Member since Oct 2011
70 posts
Vielen lieben Dank :)
Famous
Member since Oct 2011
70 posts
[Image: http://img15.imageshack.us/img15/15/1359738971208.jpg]

Uploaded with ImageShack.us

Sieht der Graph am Ende so aus? Es fehlt nur die Kante von 4 nach 3 mit Länge 10...Kann das sein?
Und noch eine Frage: Bei Knoten 3 ist der Vorgänger 1 und Nachfolger 5. Die neue Länge ist 13 und die alte ist 18. Aber die alte Länge hätte auch 11 sein können, wenn ich über Knoten 4 laufen würde. Wie enscheidet man bei so einem Fall, welchen Pfad man nimmt? Nimmt man den längeren? Oder läuft man hier über 2, weil dieser schon bearbeitet wurde?

Danke schonmal :)))
This post was edited on 2013-02-01, 19:10 by Famous.
Famous
Member since Oct 2011
70 posts
[Image: http://img443.imageshack.us/img443/5815/1359742051544.jpg]

Uploaded with ImageShack.us

Hallöchen,

mir bereitet die Implementierung von Floyd noch ein paar Probleme. Ich versteh diese 3fach geschachtelte Schleife nicht.... Vorallem diesen Vergleich.
Ich weiss, dass die erste schleife für den Knoten selber, die zweite für den Vorgänger und die dritte für den Nachfolger steht. Kann mir jemand helfen?
Ich habe die Implementierung aus der Vorlesung komplett übernommen und mir diese Mainmethode geschrieben.
Danke :)
meisterT
Member since Nov 2005
994 posts
Code als Screenshot ist nicht schoen. Nimm nimmer code-tags.

Der Vergleich in der Schleife fragt ab, ob der Pfad ueber den "Umweg"-Knoten i billiger ist als direkt von j nach k.
FAU Online Judge
rootzlevel
Avatar
Member since Oct 2009
42 posts
+2 RyanCarmon, malte
Für's nächste Mal: http://instacode.linology.info/
L. F. Ant
Avatar
Member since May 2011
1164 posts
In reply to post #8
[Image: http://cdn.memegenerator.net/instances/400x/25386126.jpg]


Trotzdem:
  1. if (g[j][i] + g[i][k] < g[j][k])
Da schaust du, ob die Summe der Wegkosten von Knoten j nach i und von i weiter nach k kleiner ist, als die momentan für den Weg von j nach k gespeicherten Kosten. Wenn's über Knoten i schneller geht, dann aktualisierst du die Kosten anschließend.
Die Schleifen sind dann einfach dazu da, alle Wegkombinationen systematisch durchzutesten, sodass am Ende zwischen allen Knotenpaaren die geringsten Kosten stehen.

So und nun eine Frage von mir: Was bringt einen dazu, seinen Code vom Bildschirm abzufotografieren, das Bild irgendwo hochzuladen, nur um dann das Foto im Forum zu verlinken, wenn es auch Ctrl+C und Ctrl+V getan hätte??? :D
Your argument is irrelephant.
This post was edited 2 times, last on 2013-02-01, 19:41 by L. F. Ant.
Famous
Member since Oct 2011
70 posts
Tut mir echt leid leute...ich lerne seit über 10 Stunden, mein Kopf ist tot :D
Deshalb sorry für die ganze gaga und danke für die antworten :)
L. F. Ant
Avatar
Member since May 2011
1164 posts
Quote by Famous:
Tut mir echt leid leute...ich lerne seit über 10 Stunden, mein Kopf ist tot :D
Deshalb sorry für die ganze gaga und danke für die antworten :)

Ich wurde gut unterhalten :-p Aber primär von Wikipedia:
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         temp = dist[i][k] + dist[k][j] // This will optimize the code performance , by removing the redundant expression .
         if temp < dist[i][j] then      // Redundant code here may be like using dist[i][k] + dist[k][j] instead of using temp .
            dist[i][j] ← temp
Genious at work! :D
Your argument is irrelephant.
Airhardt
FAU-Mann
Member since Oct 2005
3262 posts
In reply to post #12
+2 Damon, Famous
Quote by Famous:
Tut mir echt leid leute...ich lerne seit über 10 Stunden, mein Kopf ist tot :D
Deshalb sorry für die ganze gaga und danke für die antworten :)
Mach ne Pause und dreh eine Runde um den Block. Hilft ungemein beim Kopf freikriegen. :-)
Ina89
Member since Jun 2012
34 posts
+1 Famous
Hallo :)

habe auch den Code aus der Vorlesung übernommen und iwie hat er nur nach einer kleiner Änderung funktioniert. Poste dir nochmal hier meinen Code, vll. hilft dir das weiter :)

public class Floyd {

    public static double[][] floyd(double [][] cost){
               
        int n = cost.length;
        double [][] g = new double[n][n];
       
        for(int j = 0; j<n; j++){
            for(int k = 0; k<n; k++){
                g[j][k] = cost[j][k];
            }
        }
       
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                for(int k = 0; k<n; k++){
                    double d = g[i][k] + g[k][j];
                    if( d < g[i][j]){
                        g[i][j] = d;
                }
            }
        }
    }
    return g;
}
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen