# Algorithmus von Warshall



## julia1997 (19. Apr 2017)

Hallo!

Kann mir jemand helfen?


----------



## julia1997 (19. Apr 2017)

Bei a) hätte ich mir gedacht, dass Berta und Anton vielleicht nicht die gleiche Reihenfolge haben, und es trotzdem immer auf das gleiche herauskommt. Aber b) kapiere ich irgndwie nicht? welches n ist gemeint?


----------



## mrBrown (19. Apr 2017)

Vermutlich das N aus Satz 5.13


----------



## julia1997 (19. Apr 2017)

;-)


----------



## mrBrown (19. Apr 2017)

Weist du jetzt, welches N gemeint ist?


----------



## julia1997 (19. Apr 2017)

Ja aber ich verstehe trotzdem nicht genau was es zu bedeuten hat.. Steht N für die ganze Zeile?


----------



## mrBrown (19. Apr 2017)

julia1997 hat gesagt.:


> Steht N für die ganze Zeile


Nein, es ist ja `N=A` am Anfang der Schleife


----------



## julia1997 (19. Apr 2017)

N ist die Anzahl der Elemente und A die Matrix?


----------



## mrBrown (19. Apr 2017)

julia1997 hat gesagt.:


> N ist die Anzahl der Elemente und A die Matrix?



A ist die Matrix, ja. Und was ist wohl N, wenn N=A ist?


----------



## julia1997 (19. Apr 2017)

Kopie der Matrix


----------



## mrBrown (19. Apr 2017)

Genau


----------



## julia1997 (19. Apr 2017)

deswegen braucht man N am Ende, damit man beim nächsten Schritt wieder mit der "neuen" Matrix arbeiten kann?


----------



## mrBrown (19. Apr 2017)

Ja, ob man es aber überhaupt braucht ist ja die Frage


----------



## julia1997 (19. Apr 2017)

Das letzte A=N braucht man also nicht, wenn du so fragst haha


----------



## julia1997 (19. Apr 2017)

beim Algorithmus geht man ja die Zeilen und Spalten durch und am Ende wird einfach das neue A nochmal überschrieben und dass braucht es nicht unbedingt


----------



## mrBrown (19. Apr 2017)

Passiert denn noch irgendwas sinnvolles, wenn man nur das letzte A=N weg lässt?


----------



## julia1997 (19. Apr 2017)

Nein eig nicht oder? Die erste Schleife läuft weiter


----------



## mrBrown (20. Apr 2017)

Mit der ersten Schleife hat das allerdings nicht viel zu tun


----------



## julia1997 (20. Apr 2017)

Ich wüsste nicht was dann noch passieren sollte


----------



## stg (20. Apr 2017)

In Algorithmus 5.13 wird nur in der Kopie von A geschrieben und erst, wenn "alles fertig berechnet" wurde, werden alle Änderungen wieder nach A geschrieben.
Wenn du direkt in A schreibst, dann ist der Wert, der dort ursprünglich stand, weg.
Die Frage ist nun, ob du eventuell in einem späteren Schleifendurchlauf noch einmal den Wert brauchst, der ursprünglich dort stand, oder aber, ob es wichtig ist, dass der neue Wert schon dort steht und nicht mehr der alte.
Ist das nicht der Fall, so ist die Lösung von Anton natürlich "besser", in Hinblick darauf, dass sie mit hal so viel Speicher auskommt.
Das letzte A = N in 5.13 kannst du natürlich nicht einfach weglassen, sonst ist A nach dem Algorithmus ja immer noch unverändert.


----------



## julia1997 (20. Apr 2017)

Vielen vielen vielen Dank!


----------



## julia1997 (20. Apr 2017)

Nochmal kurz zu Aufgabe a: es ist egal wo die Werte in der Matrix stehen, das ist mir klar. Aber wo ist die Stelle in der Definition mit der Wahlmöglichkeit? Man könnte j und i vertauschen?


----------



## julia1997 (20. Apr 2017)

also es ist egal, ob man spalten oder zeilenweise vorgeht


----------



## mrBrown (20. Apr 2017)

Ja, das ist egal


----------

