Erreichbarkeitsmatrix M* mit dem Algorithmus von Warshall

Aufrufe: 520     Aktiv: 16.04.2022 um 20:20
0
Hallo alle zusammen,

ich verstehe leider nicht, wie man bei der Aufgabe vorgehen soll.
Könnte mir jemand die einzelnen Schritte erklären?

Vielen Dank im voraus!

Diese Frage melden
gefragt

Student, Punkte: 148

 
Der Warshall-Algorithmus wird zur Bestimmung der kürzesten Wege in einem gerichteten Graphen verwendet … Ich bin mir nicht sicher ob du bei informatikfragen.de eher eine hilfreiche Antwort dazu erhältst … es kommt zwar aus der theoretischen Informatik und es kann durchaus sein das ein Mathematiker dir hier weiter helfen kann … aber vielleicht schaust du dir mal selbst ein Beispiel im Internet an, wie die Matrizen $W_i$ aus dem Algorithmus entstehen … bzw. hast du dazu doch bestimmt in deinen Unterlagen stehen wie der Algorithmus funktioniert, wenn von dir anscheinend verlangt wird diesen anzuwenden … aus der ersten Matrix $W_0$ solltest du auf jedenfall deinen ausgangsgraphen ablesen können   ─   maqu 16.04.2022 um 19:58
ich kann jedes Wort von cauchy unterschreiben ... und wenn du am Anfang noch Probleme mit der Notation hast dann wie gesagt sich einmal den Graphen vor Augen führen und den Hinweisen von mikn nachgehen (auch am Graph) um nachzuvollziehen was in jedem schritt gemacht wird   ─   maqu 16.04.2022 um 20:20
Kommentar schreiben
1 Antwort
0
Das ist eine Frage für Mathematik (Graphentheorie) und Informatik. Man kann sie in beiden Foren stellen, aber eben bitte nicht zweimal im gleichen Forum.
Auf https://www.inf.hs-flensburg.de/lang/algorithmen/graph/warshall.htm dort im Abschnitt Idee, ist der Algorithmus ganz gut (finde ich) erklärt. Den solltest Du Schritt für Schritt mit Beispiel 6.1 durchgehen.
(i,k) und (k,j) sind Kanten heißt einfach, dass an diesen Positionen in der Matrix Einsen stehen. Die eine in Zeile i, die andere in Spalte j, und das wird für alle k durchlaufen. Daher ist im Beispiel die k-te Zeile rot und die k-te Spalte grün markiert.
Und nun fang mal einfach an. Das sieht am Anfang kompliziert aus - aber nur solange man nicht anfängt. Danach wird es klarer. Auf geht's.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.86K

 

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.