Vorgängermatrix bei Floyd Warshall Algorithmus. Grüne Felder bei 1.4 richtig?

Question

ich studiere Informatik im 1. Semester und bin gleich mal durch die vermaledeite Algebra Klausur gerasselt... Nun habe ich also die Ehre, erneut anzutreten und lerne wie ein blöder.

Leider hänge ich seit 3 Tagen am Floyd Warshall Algorithmus (um genau zu sein an der Erzeugung der Vorgänger- /π Matrix).

Wie man die Distanzmatrix erzeugt weiß ich inzwischen, allerdings brauche ich eure Hilfe / Erklärung für o.g. Problem, denn Youtube und zahlreiche Erklärungen im Netz behandeln entweder gar nicht die Vorgänger-Matrix oder so, dass ich das Problem nicht lösen kann.

Im Anhang einer der Graphen, die mir Probleme machen. Besonders bei I.4− dort habe ich die Stellen grün markiert, die ich eigentlich mit 4 gefüllt hätte...

Ich wäre euch sehr dankbar, wenn wir gemeinsam meine Denkblockade weg bekommen :-)

Semper

Comments

Kannst du das, was du weisst, etwas genauer erklären? 

Wie kommen z. B. die Bildchen 1.0, ... 1.5 zustande? 

Answer 1

Hi, vielen Dank für Deine Antwort.

Das sind die Iterationen über die Wegpunkte.

edit: 

die Frage hat sich erledigt... ich muss einfach in der vorherigen Vorgängertabelle schauen, wie komme ich von einem Punkt zum anderen...

Vielleicht hilft es ja anderen:

1. wird der Weg kürzer, wenn ich von 3 zu 1 über 4 gehe (ja). 3->4->1
Aber wie komme ich dann von 4 -> 1 (laut Vorgängertabelle über die 2) also 3->4->2->1...
Daher wird hier 2 eingetragen.

2. wird der Weg kürzer, wenn ich von 5 zu 1 über 4 gehe (ja). 5->4->1
Aber wie komme ich dann von 4 -> 1 (laut Vorgängertabelle über die 2) also 5->4->2->1...
Daher wird auch hier 2 eingetragen.

-----------

Comments

Danke für die Erklärung. Habe nun daraus ausnahmsweise eine Antwort gemacht.